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.
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
is pretty much the standard reference for NP-completeness, will a substantial list of NP-complete problems. Computational Complexity
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)