Reddit reviews Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences)
We found 10 Reddit comments about Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). Here are the top ones, ranked by their Reddit score.
Used Book in Good Condition
Jeff Atwood is a certified imbecile.
if you read his past blogs on CS theory, he completely misunderstands the whole topic at hand and posts amazon-referrer links to books he has obviously never read and likely lacks the capability to comprehend.
http://blog.codinghorror.com/your-favorite-np-complete-cheat/
he strongly recommends this book. (and provides his referrer link)
Computers and Intractability: A Guide to the Theory of NP-Completeness
www.amazon.com/dp/0716710455/
and then makes this comment.
>The theory of NP-completeness provides many straightforward techniques for proving that a given problem is just as hard as a large number of other problems that are widely recognize as being difficult and that have been confounding the experts for years. Armed with these techniques, you might be able to prove that the bandersnatch problem is NP-complete and march into your boss's office and announce: I can't find an efficient algorithm, but neither can all these famous people.
>--
>I guess I make a distinction between reducing problem to another known NP-complete problem and proving a problem is NP-complete. Apparently we can't prove anything is NP-complete, we can only throw a wall of experts at it and see them all fail.
>So, a NP-complete problem is not mathematically proven, it's one that no experts can solve, eg, I'll know it when I see it.
>Or more specifically we'll know it when lots of experts have seen it, tried, and failed.
>Is this wrong?
this guy is a joke.
there are a few more gems if you bother to look around there too.
A few of my favorites:
If you're interested in this subject and want to broaden your arsenal of known NP-complete problems, I highly recommend the book "Computer and Intractability" by Garey and Johnson. It's a classic text in this area and a great place to go when you're faced with a new problem and are looking for something to reduce to it. Wikipedia also has a nice list of NP-complete problems. To become "efficient" at reductions, you really just have to do a lot of them, to recognize the types of patterns that commonly occur and the types of widgets that tend to work. Of course, even then, sometimes coming up with a reduction for a new problem is incredibly challenging — often such things lead to papers if the problem you're reducing to is an interesting one whose hardness has not yet been proven.
If you get interested and actually want to learn more about this subject, this is the book you want. Most of wikipedia's proofs like on the Cook-Levin theorem page are heavily borrowed from there, but are not nearly as well written. Provided you've had some reasonable undergraduate maths exposure Gary and Johnson will be a great read and is a relatively short book (although it took me multiple readings and manually working through a few of the proofs before I had a conceptual understanding of why they worked).
Qualifier: it's been years since I've done any CC stuff, so be aware that I might be leading you down the wrong track here. That aside, here're the approaches that feel 'right':
(1) Come up with a way to transform a general graph to one with max degree 2q-1, in such a way that one is q-colourable iff the other is. Search for 'graph gadgets', or alternatively find a copy of Garey & Johnson.
(2) Edit: this one I'm less sure of.
All the suggestions above a really good! I'd like to suggest a couple more; I
think these are necessary for a Computer Science god, if not a programming one.
Concrete Mathematics by Knuth & Patashnik
Computers and Intractability by Garey & Johnson.
That's all for now...
It was more historical research on instrumental theorems in Set Theory. It was about the development, statement, and eventual proof and its consequences. Started at Cantor, then to Hilbert, and eventually Godel which was the focus. It was mostly fueled out of people misunderstanding the implications of the proof. Popular culture surrounding Godel's theorem is 90% wrong and atrocious, even with famous and influential books like GEB.
As for your research, no offense but it seems daunting. Proving that a statement is undecidable is incredibly hard work. It's easier to create an undecidable statement then it is to prove a statement is undecidable! (The proof of Godel's Theorem utilizes this idea).
And based upon your last statement I highly, HIGHLY, recommend reading this book: http://www.amazon.com/Godels-Theorem-Incomplete-Guide-Abuse/dp/1568812388
It's a great read and will clear up a lot of misconceptions about the theorem.
Since you are dealing with modeling you more than likely are going to be dealing with computable systems and while related to Set Theory you'd probably want to look more into NP-Completeness and Cook's Theorem. Not as complete an answer considering P=NP is possibly the biggest open question of the day, but proving something is NP Complete may have very similar results to what you are looking to do, and IMHO is much easier to do than proving a statement is undecidable. For instance here is a book of NP Completeness proofs: http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455
and was compiled and written shortly after Cook's Theorem was published.
whereas proving that the Continuum Hypothesis was undecidable took 63 years!
http://en.wikipedia.org/wiki/Continuum_hypothesis
So as I was saying, it is hard to prove something is undecidable.
Well, canon would be Garey & Johnson, but it's a bit behind the times. Arora & Barak as /u/DarkSayed suggests, Papadimitriou, and Sipser are all good alternatives.
Garey and Johnson, Computers and Intractibility A tour of NP-complete problems
Probably part of the problem is that lots of practical programming is quite trivial from an algorithmic point of view, though it can be really difficult anyway. Nowadays if you are coding interactive menus and all that, the packages and code architectures can be very complex. Or managing threads, networking, etc. All the subtleties of exception handling etc. But almost none of this is algorithmically challenging.
The real fun starts when you need to solve a problem and all the obvious approaches take hours or days or weeks of program execution time or maybe the memory requirements skyrocket. Is there a clever way to write code that runs faster or in less space, or is the problem just inherently hard?
http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455/ might be useful to look at.
A lot of the language thing has to do with memory requirements. If you can solve a problem with a Finite State Automaton, then you know you don't have any memory problem at all!