## 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, P^{A} ≠ NP^{A} ≠ co-NP^{A} 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)