12
$\begingroup$

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?

$\endgroup$
1

10 Answers 10

11
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ Thank you for your words of wisdom. If I am entirely honest, the more I learn about the problem the more impossible it seems for somebody to find a solution. Certainly very interesting though! $\endgroup$
    – Jon Cox
    Dec 10, 2010 at 22:09
  • 4
    $\begingroup$ +1 I like it but let me disagree. $P vs NP$ is no monster but a very beautiful babe waiting for someone to lift her veil so the world can enjoy her glorious beauty. Besides, she is very innocent and pure and she is just trying to play with us and tease us with her puzzles all the time ... $\endgroup$ Dec 12, 2010 at 4:03
  • 2
    $\begingroup$ Also, if she was a monster I would immediately quit pursuing her because I hate monsters :) $\endgroup$ Dec 12, 2010 at 4:09
9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for the suggestion, I'll shall get a copy from the library and will have be having a look through it :) $\endgroup$
    – Jon Cox
    Dec 10, 2010 at 10:46
7
$\begingroup$

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. :-)

$\endgroup$
2
  • 7
    $\begingroup$ appears to be hard is an highly-over-underestimate description to the hardness of P vs NP. :) $\endgroup$ Dec 10, 2010 at 3:40
  • $\begingroup$ Thank you for the suggestion, there are a good number of materials to check out there. $\endgroup$
    – Jon Cox
    Dec 10, 2010 at 10:43
7
$\begingroup$

Here is one of the best survey articles about the P vs NP problem, $P$, $NP$ and mathematics – a computational complexity perspective, by Wigderson

$\endgroup$
1
  • $\begingroup$ Thank you for an excellent link, I will be adding this my lengthening reading list of excellent materials relating to the problem :) $\endgroup$
    – Jon Cox
    Dec 10, 2010 at 10:49
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Excellent, I already have a copy of the Klienberg Tardos book for a course I do, and I shall be getting Garey and Johnson's book from the library later today. Thank you for letting me know about it. $\endgroup$
    – Jon Cox
    Dec 10, 2010 at 10:45
3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Sayin Abuzer yakaryilmaz... The second book you suggested is available on his website for free. $\endgroup$
    – Tayfun Pay
    Aug 4, 2012 at 15:27
  • $\begingroup$ geekster-- think you are mistaken. he has a blog with the same name but it doesnt have the book $\endgroup$
    – vzn
    Aug 4, 2012 at 19:35
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for letting me know about this article, it definitely looks like it's worth a read. $\endgroup$
    – Jon Cox
    Dec 10, 2010 at 10:47
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for those links. It is particularly interesting to note the current thoughts and predictions of people with much knowledge of P vs NP. $\endgroup$
    – Jon Cox
    Dec 10, 2010 at 22:10
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.