Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I was recently reminded about the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as explained by Stephen A. Cook on Clay Mathematics Institute.
It has piqued my interest and I would like to learn more about it. The first step would be gaining a deeper understanding of the problem and an understanding of the area in general.
Can you recommend any books or other resources where I can learn more about the problem?
It's good to see a fellow undergrad in pursue of this great problem, with such an enthusiasm. Allow me to offer you a piece of advice from my own experiences.
$ P \neq NP $ is a very interesting problem. The implications of the answer are immense, especially in the case that the two classes are equal. The reward is great in many levels, from the altruistic scientific one to the materialistic money award. That leads many young people that encounter the problem in trying to solve it, with no or limited knowledge about it.
Perhaps most theory students go through that phase. You will have an idea and think it is right, but it is almost certain that you are wrong. Some people never get through that phase and embarrass themselves by being too stubborn to admit their errors.
In FOCS 2010, Rahul Santhanam compared the $ P \neq NP $ question to a mythical monster. It would take many sacrifices and courage to even try to defeat this monster. After all, it may be the most difficult problem ever. To have a fighting chance, you will have to study a lot about this problem and complexity in general. You'll never know what the "monster's weakness" will be.
So my advice is this: Take your time in knowing the problem. Every time you figure out a solution, assume you are wrong somehow and try to find the problem with it. That way you'll learn much.
As for references, I would recommend Sipser's book as well. After finishing it, I would recommend "Computational Complexity:A modern approach" by Arora and Barak, a more complexity-oriented book, that requires a good understanding of the concept of computation.
I strongly suggest Sipser's "Introduction to the Theory of Computation," particularly because it covers at least one of the main barriers to resolving P vs. NP, namely relativization. It contains a very clear proof of the Baker-Gill-Solovay result. I am not sure if it contains anything on the Razborov-Rudich results, but it's a fantastic, very clear, and easy to read introductory resource for learning not only about P vs. NP but for many other related topics in complexity theory as well...which is significant because if your interest is in trying to resolve the problem, you'll want to have some background in the field and ideas for where to start.
Probably the best collection of links in one place is the Further Reading section of the wiki that was put together to help assess Deolalikar's claimed proof that $P \neq NP$.
Good luck. The problem appears to be hard. :-)
Here is one of the best survey articles about the P vs NP problem, $P$, $NP$ and mathematics – a computational complexity perspective, by Wigderson
The classic reference for NP completeness is Garey and Johnson's book (http://tinyurl.com/2w5yofs). It's both instructive and thorough.
Personally, I learned from Kleinberg Tardos (http://tinyurl.com/37dtyyl), because my University used it.
I would also suggest to take a problem instance and try to solve it. It is a good practice to experiment with open problems. By experiment I mean, you can write programs or implement known algorithms by others and understand how they work, where they fail etc. Also, you can discover several proof techniques. Remember, they won't put you in jail if you study and work a lot on this and can't find any solution. On the contrary, your competency level is guaranteed to increase.
In most cases, these problems in general are hard to solve than their specific instances. Read about NFL to get an idea.
In my case I had been soon buried under a pool of ideas and related concepts. There are programming/coding tweaks and there are theoretical maneuvers. As for example, if you want to solve any problem instance using Genetic Algorithm concepts, you would soon discover, GA alone is a vast world to discover! I've recently come to know about Linkage Learning in GA/EA. Don't know much about it though.
Additionally, when you'd try to code things up, you'd find some programming languages/tools are better/easier than others. I was lost into the discussion of, why Alex Stepenov thinks OOP is mathematically incorrect and what is the advantage of functional programming. I don't have the trail but I clearly remember, at the start I was studying an NP-Complete/Hard problem.
I welcome you, as the journey is albeit adventurous!
P, NP, and NP-Completeness: The Basics of Complexity Theory by Oded Goldreich would be an another good introductory book.
After introductory contents, I would like to also recommend The P=NP Question and Gödel’s Lost Letter by Richard J. Lipton.
I recommend the excellent review article by Lance Fortnow, "The Status of the P versus NP Problem", which discusses some new approaches to the problem.
You could read the well-known paper by W. Gasarch concerning poll on the question $P=?NP$, another good read is "Why is $\mathcal{P}$ Not Equal to $\mathcal{NP}$?" (and see references in it) by M. Fellows and F. Rosamond.
Lance Fortnow recently expanded and published his already-comprehensive column from CACM (mentioned in MA's other answer) into a full length popular-science level book, The Golden Ticket: P, NP, and the Search for the Impossible. it was reviewed in the New Yorker, "A most profound math problem", by Nazaryan. (publishers page, Princeton University Press)
