P v NP - useful books
The topic of NP completeness is part of the subject of computational complexity, and most books on this subject will require some technical knowledge on the part of the reader. However, the situation isn't as bad as with some subjects where serious books seem totally opaque to the uninitiated. Most people reading this will be familiar with computers, and probably with programming to some degree. This means that even fairly technical books can usually be understood, at least in part.
Books for the general reader
If you do feel that you need an introduction to the subject which isn't too technical then there are a couple of suitable books.
Computers Ltd., what they really can't do by
David Harel is a short overview of the limitations of computers, and includes a chapter on NP completeness.
Keith Devlin has written
The Millennium problems : the seven greatest unsolved mathematic, which looks at each of the seven Millennium prize problems, and is aimed at a non-technical audience.
Undergraduate-level books
There are several books which are designed for undergraduate computer science courses, but again I would emphasis that if you have a good knowledge of programming then you shouldn't have any problems with them.
Algorithmics : the spirit of computing by
David Harel covers much over the same material as
Computers Ltd. but at a deeper level.
Introduction to the theory of computation by
Michael Sipser has plenty of diagrams making it easy to follow.
Fundamentals of algorithmics by
Gilles Brassard looks more textbooky to me.
More advanced books
To get a more detailed view of the subejct you will need to consult a more advanced textbook.
Computers and Intractability by
Garey and
Johnson is pretty much the standard reference for NP-completeness, will a substantial list of NP-complete problems.
Computational Complexity by
Papadimitriou is a useful source for finding out what lower bounds on the running times of algorithms
have been proved.
The theory of computation by
Bernard Moret seems to give more discussion of results, with not so much in terms of proofs, but assumes a graduate level knowledge of the subject.
Online Resources and papers
As usual there is a Wikipedia page on this subject:
Complexity classes P and NP. For the current position you should look at
The P-versus-NP page . This links to proofs of both P=NP and P≠NP, so you shouldn't take all of the links too seriously.
There is speculation that P=NP might be formally undecidable in the paper: Relative to a Random Oracle A, PA ≠ NPA ≠ co-NPA with Probability 1; Charles H. Bennett, John Gill SIAM J. Comput. 10(1): 96-113 (1981) . Although I said that this would not be significant, you might still be interested in the discussions in the following paper: Is P Versus NP Formally Independent?
The demonstration that P=NP can't be settled with a diagonalization argument is given in:
Relativizations of the P =? NP question T. Baker, J. Gill, and R. Solovay SIAM J. Comput, 4(4) 431-442, (1975)
