Gaining Mid-level Understanding of P vs NP

Question

I have a base understanding of N and NP, but I want to find some material to gain a better understanding to it. E.g. 'Mid-level', something that goes more into depth of it. Any suggestions for PhD papers to read or books for a better understanding?

Answer 1

You should read the later chapters (4–7) of Garey and Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. It is old but still good.

It discusses many of the finer points of NP-completeness, such as number problems and pseudo-polynomial-time algorithms, #P-completeness, and the reasons why no resolution of $P=NP$ should be expected soon.

Answer 2

I also recommend “Shtetl-Optimized”, the blog of Scott Aaronson, who is a computer science researcher affiliated with MIT. For example, this recent article on The Scientific Case for P≠NP.

Answer 3

I believe Sipser's classic "Introduction to the theory of computation" can give you a solid base for P vs NP and computational complexity in general. It starts fram the basics like languages and the definition of a Turing machine and goes on to more interesting theory. The good with this book is that many times it skips any unnecessary formalities.