Why are you trying to explode your brain? Do you not like it?

The obvious answer -- which is probably a good introduction for someone who has some math but not enough to have covered this in class -- is Gödel, Escher, Bach: An Eternal Golden Braid There's a part of the book that does discuss it but I don't recall in how much detail. OK, Amazon search doesn't turn it up, but there is an entire chapter on completeness.

Another source would be the bibliography at Wikipedia.

I have Godel, Escher, Bach! Trying to read it didn't go...well.

But the Wikipedia bibliography is a good idea. Durr.

Ugh, my brain hurts just reading the titles of, and seeing the price of, some of these Neil Immerman books. Yow.

CITR, The radio station at The University of British Columbia has all kinds of Podcasts of all different kinds of music

GEB does not talk about this at all, and the sort of completeness that's discussed there has no (direct) relation to NP-completeness.

I actually can't recommend a good, accessible book about this, and I believe that there's a reason for that, which is that it is not a good, accessible problem. I think it's a very artificial problem, which is a subjective judgement to be sure, but some problems feel like they arise naturally and would be universal problems that any mathematically-aware culture would study; others feel like they are concerned with a more arbitrary matter: they have a quirk of representation at their heart. P vs NP falls into the latter case for me. That doesn't mean it's not a real, and difficult problem to be solved; but problems of this type tend to be less "grabby" because understanding them past the most superficial, press-blurb level involves understanding some very technical definitions that don't have a particularly organic, easily-motivated origin.

I will tell you one thing about this which tends to muddy the waters a great deal in elementary discussions of the problem (mentioned here in the "One caveat" paragraph). To even discuss whether a particular 'problem' is P or NP, that problem has to come in a family of problems, of ever-increasing sizes. The P or NP (or other complexity) status of the problem is a statement of how fast the time required to solve the problem grows, as the problem grows in size.

What you will usually see in an expository account of complexity theory is a statement like "Playing chess is NP hard", which MAKES NO SENSE WHATSOEVER and can make you feel stupid for not understanding it. What people mean when they say that is "We have a set of rules in mind that lets you play chess on boards not only 8x8, but also on larger size boards: 9x9, 10x10, 11x11, and so on, as large as you'd like (with more pieces and suitably adapted rules for each size). As you increase the board size, the time it takes for a good algorithm to find a winning move increases not just linearly (so it would take as long to produce a winning move on an 16x16 board as on the 8x8) or even quadratically (meaning a 16x16 board would take 2^2=4 times as long as an 8x8, and a 24x24 board would take 3^2=9 times as long as the 8x8), or even cubically... the time required grows faster than any of those patterns.

Some famous NP-complete problems, and their notion of size:

The Travelling Salesman problem: as the number of cities grows, the time required to find a good route increases ridiculously fast.

3SAT: as the number of free variables increases, the time required to see if the formula can be satisfied increases ridiculously fast.

Knapsack Problem: As the number of items to choose from increases, the time required to see if the formula can be satisfied increases ridiculously fast.

Dots and Boxes: As the number of dots in the game increases, the time required to choose a winning move at any point... etc.

The actual P vs NP problem, in a nutshell, is this: in each of the examples I've mentioned, what I _really_ mean is "the time required to solve the problem, using the best algorithm known, increases ridiculously fast as a function of the size of the problem". The vexing bit is whether there might be a really super-clever algorithm, for, say, solving the travelling salesman problem, whose time requirements don't grow so rapidly as the size of the problem increases. If you think "NP is not P" then you think that there is no such super-clever algorithm, and even the best strategy for solving the travelling salesman problem will always be subject to catastrophically fast growth in the amount of time it requires. This is probably the majority opinion at the moment. If you think that "NP is P" then you think that there is a super-clever algorithm for the travelling salesman problem which won't suffer this kind of horrible increase in time requirements as the size of the problem grows.

The latter situation would be remarkable because Travelling Salesman enjoys "NP complete" status, which means (quite informally) that any of the other problems I've mentioned can be solved 'quickly' if Travelling Salesman can be. (A major - and majorly boring - pastime in the field of computational complexity is to show how one particular problem can be reformulated in the language of another problem. If your favorite problem is 3SAT, and somebody knows a fast algorithm for solving Travelling Salesman, there is a Theory of Computation expert out there who will look at your 3SAT problem, draw an appropriate graph, use the fast Travelling Salesman algorithm to produce a path, and then translate that path back into a solution to your 3SAT problem.)

It's not a book, but I hope that helps. My feelings are that deciding the P vs. NP problem is going to require really revolutionary insights, so it's an exciting problem for the ancillary effects it's likely to have, but the actual problem itself (and the answer to it) are unlikely to be very interesting. And that's what I'm afraid you'll find if you try to delve deeper into it than what I've sketched out here - it will quickly descend into a mass of stiff, technical definitions with almost no 'pretty' results to reward the effort, and the state of the art is that really nobody has a clue how to proceed about answering the big question. It is not like, for example, the Riemann Hypothesis, which is also a very difficult problem but has a very rich tapestry of partial results and lots of current, promising active lines of attack.

Wolfdog, that was great, I would totally buy your book!

I like Garey and Johnson

But, better still, I will prove P doesn't equal NP right here in metachat.

I will do this by showing that the subset sum problem does not have a polynomial solution. Well, not really, but a problem like the subset sum problem.

I like the subset part, but the sums make the original problem too weird. Knowing the sum of one subset tells you something about the sums of other subsets but it's not quite clear how much information you get from it. Imagine if we could change the problem so that we knew we got no information about the other subsets from a particular subset. To do this, instead of using sums (a sum is really a function which maps an arbitrary number of values to a single value) we invent a new function called blackbox(). It assigns some integer to any set of integers but it does it in some funky way that doesn't tell you anything about what it would give you had you fed it a different set of integers.

The new problem is, given a set of n integers, is there any subset of these integers such that blackbox() applied to it returns zero?

Since the function is designed to give no information, the only way to answer the question is to try all subsets. This is exponential, not polynomial (there are 2^n subsets of a set of size n). But this is in NP since if you had such a subset, you can verify it by just trying it.

Thanks, Obscure Reference! I put a used copy in my cart!

I hear talks of a boycott by my brain against the rest of me, particularly those nasty typing fingers.