<p>Probably the best collection of links in one place is the <a href="http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper#Further_reading">Further Reading section</a> of the wiki that was put together to help assess Deolalikar's claimed proof that $P \neq NP$.</p>

<p>Good luck.  The problem appears to be hard. :-)</p>

CC BY-SA 2.5
2010-12-10T03:40:31.650Z
*appears to be hard* is an highly-over-underestimate description to the hardness of P vs NP. :)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-10T10:43:57.463Z
Thank you for the suggestion, there are a good number of materials to check out there.
Jon Cox
CC BY-SA 2.5
2010-12-10T03:32:20.440Z
2010-12-10T03:32:20.440Z
Aaron Sterling
<p>Here is one of the best survey articles about the P vs NP problem, <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf">$P$, $NP$ and mathematics – a computational complexity perspective</a>, by Wigderson </p>

CC BY-SA 2.5
2010-12-10T10:49:42.623Z
Thank you for an excellent link, I will be adding this my lengthening reading list of excellent materials relating to the problem :)
Jon Cox
CC BY-SA 2.5
2010-12-10T08:40:33.413Z
2010-12-10T08:50:44.873Z
2010-12-10T08:50:44.873Z
Mohammad Al-Turkistany
<p>The classic reference for NP completeness is Garey and Johnson's book (http://tinyurl.com/2w5yofs). It's both instructive and thorough. </p>

<p>Personally, I learned from Kleinberg Tardos (http://tinyurl.com/37dtyyl), because my University used it.</p>

CC BY-SA 2.5
2010-12-10T10:45:06.090Z
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.
Jon Cox
CC BY-SA 2.5
2010-12-10T03:14:01.730Z
2010-12-10T03:21:49.803Z
2010-12-10T03:21:49.803Z
Gautam Kamath
<p><a href="http://www.wisdom.weizmann.ac.il/~oded/bc-book.html" rel="nofollow">P, NP, and NP-Completeness: The Basics of Complexity Theory</a> by Oded Goldreich would be an another good introductory book.</p>

<p>After introductory contents, I would like to also recommend <a href="http://www.springer.com/computer/theoretical+computer+science/book/978-1-4419-7154-8" rel="nofollow">The P=NP Question and Gödel’s Lost Letter</a> by Richard J. Lipton.</p>

CC BY-SA 3.0
2012-08-04T15:27:28.573Z
Sayin Abuzer yakaryilmaz... The second book you suggested is available on his website for free.
Tayfun Pay
CC BY-SA 3.0
2012-08-04T19:35:28.493Z
geekster-- think you are mistaken. he has a blog with the same name but it doesnt have the book
vzn
CC BY-SA 3.0
2012-08-04T13:23:34.937Z
2012-08-04T13:23:34.937Z
Abuzer Yakaryilmaz
<p>I recommend the excellent review article by Lance Fortnow, <a href="http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext" rel="nofollow">"The Status of the P versus NP Problem"</a>, which discusses some new approaches to the problem.</p>

CC BY-SA 2.5
2010-12-10T10:47:59.410Z
Thank you for letting me know about this article, it definitely looks like it's worth a read.
Jon Cox
CC BY-SA 2.5
2010-12-10T07:03:20.320Z
2010-12-10T07:03:20.320Z
Marko Amnell
<p><a href="http://en.wikipedia.org/wiki/Lance_Fortnow" rel="nofollow">Lance Fortnow</a> recently expanded and published his already-comprehensive column from CACM (mentioned in MA's other answer) into a full length popular-science level book, <a href="http://rads.stackoverflow.com/amzn/click/0691156492" rel="nofollow">The Golden Ticket: P, NP, and the Search for the Impossible</a>. it was reviewed in the <a href="http://www.newyorker.com/online/blogs/elements/2013/05/a-most-profound-math-problem.html" rel="nofollow">New Yorker, "A most profound math problem"</a>, by Nazaryan. (<a href="http://press.princeton.edu/titles/9937.html" rel="nofollow">publishers page</a>, Princeton University Press)</p>

CC BY-SA 3.0
2013-09-10T19:11:49.470Z
2013-09-10T19:11:49.470Z
vzn
<p>You could read the well-known paper by W. Gasarch concerning poll on the question <a href="http://www.cs.umd.edu/~gasarch/papers/poll.pdf" rel="nofollow">$P=?NP$</a>, another good read is "<a href="http://mrfellows.net/papers/C73.pdf" rel="nofollow">Why is $\mathcal{P}$ Not Equal to $\mathcal{NP}$?</a>" (and see references in it) by M. Fellows and F. Rosamond.</p>

CC BY-SA 2.5
2010-12-10T22:10:53.953Z
Thanks for those links. It is particularly interesting to note the current thoughts and predictions of people with much knowledge of P vs NP.
Jon Cox
CC BY-SA 2.5
2010-12-10T20:38:59.693Z
2010-12-10T20:38:59.693Z
Oleksandr Bondarenko
<p>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>

<p>$ 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. </p>

<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-10T22:09:28.573Z
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!
Jon Cox
CC BY-SA 2.5
2010-12-12T04:03:40.607Z
+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 ...
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-12T04:09:43.360Z
Also, if she was a monster I would immediately quit pursuing her because I hate monsters :)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-10T19:43:18.393Z
2010-12-10T19:43:18.393Z
chazisop
<p>I was recently reminded about the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as <a href="http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf">explained</a> by Stephen A. Cook on Clay Mathematics Institute.</p>

<p>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.</p>

<p>Can you recommend any books or other resources where I can learn more about the problem?</p>

CC BY-SA 2.5
2010-12-10T15:50:40.950Z
Crossposted from http://math.stackexchange.com/questions/13742/resources-to-learn-about-the-p-vs-np-problem, which has currently no answers.
Tsuyoshi Ito
<cc.complexity-theory><reference-request><survey><books><p-vs-np>
Resources to learn about the P vs. NP problem
Jon Cox
# Resources to learn about the P vs. NP problem

(Asked by: username_0 on 2010-12-10)

I was recently reminded about the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as [explained](http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf) 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?

**Tags:** cc.complexity-theory, reference-request, survey, books, p-vs-np

> **Comments:**
> **username_1**: Crossposted from http://math.stackexchange.com/questions/13742/resources-to-learn-about-the-p-vs-np-problem, which has currently no answers.  

---

## 8 answers

### Answer by username_11 on 2010-12-10. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_0**: 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!  
> **username_4**: +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 ...  
> **username_4**: Also, if she was a monster I would immediately quit pursuing her because I hate monsters :)  

---

### Answer by username_2 on 2010-12-10. Score: 7

Probably the best collection of links in one place is the [Further Reading section](http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper#Further_reading) 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. :-)

> **Comments:**
> **username_3**: *appears to be hard* is an highly-over-underestimate description to the hardness of P vs NP. :)  
> **username_0**: Thank you for the suggestion, there are a good number of materials to check out there.  

---

### Answer by username_4 on 2010-12-10. Score: 7

Here is one of the best survey articles about the P vs NP problem, [$P$, $NP$ and mathematics – a computational complexity perspective](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf), by Wigderson

> **Comments:**
> **username_0**: Thank you for an excellent link, I will be adding this my lengthening reading list of excellent materials relating to the problem :)  

---

### Answer by username_5 on 2010-12-10. Score: 4

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_6 on 2012-08-04. Score: 3

[P, NP, and NP-Completeness: The Basics of Complexity Theory](http://www.wisdom.weizmann.ac.il/~oded/bc-book.html) 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](http://www.springer.com/computer/theoretical+computer+science/book/978-1-4419-7154-8) by Richard J. Lipton.

> **Comments:**
> **username_7**: Sayin Abuzer yakaryilmaz... The second book you suggested is available on his website for free.  
> **username_8**: geekster-- think you are mistaken. he has a blog with the same name but it doesnt have the book  

---

### Answer by username_9 on 2010-12-10. Score: 2

I recommend the excellent review article by Lance Fortnow, ["The Status of the P versus NP Problem"](http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext), which discusses some new approaches to the problem.

> **Comments:**
> **username_0**: Thank you for letting me know about this article, it definitely looks like it's worth a read.  

---

### Answer by username_8 on 2013-09-10. Score: 2

[Lance Fortnow](http://en.wikipedia.org/wiki/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](http://rads.stackoverflow.com/amzn/click/0691156492). it was reviewed in the [New Yorker, "A most profound math problem"](http://www.newyorker.com/online/blogs/elements/2013/05/a-most-profound-math-problem.html), by Nazaryan. ([publishers page](http://press.princeton.edu/titles/9937.html), Princeton University Press)


---

### Answer by username_10 on 2010-12-10. Score: 2

You could read the well-known paper by W. Gasarch concerning poll on the question [$P=?NP$](http://www.cs.umd.edu/~gasarch/papers/poll.pdf), another good read is "[Why is $\mathcal{P}$ Not Equal to $\mathcal{NP}$?](http://mrfellows.net/papers/C73.pdf)" (and see references in it) by M. Fellows and F. Rosamond.

> **Comments:**
> **username_0**: Thanks for those links. It is particularly interesting to note the current thoughts and predictions of people with much knowledge of P vs NP.  

---

