# P = NP problem

1. Sep 5, 2009

### Jimmy84

I was reading about the P = NP problem, and it seems very intersting because it has deep implications for math and for all of science if proven true.

(Quote)
http://en.wikipedia.org/wiki/P_=_NP_problem#Consequences_of_proof"

One of the reasons the problem attracts so much attention is the consequences of the answer.

A proof of P = NP could have stunning practical consequences, if the proof leads to efficient methods for solving some of the important problems in NP. Various NP-complete problems are fundamental in many fields. There are enormous positive consequences that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in operations research are NP-complete, such as some types of integer programming, and the travelling salesman problem, to name two of the most famous examples. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in Protein structure prediction are also NP-complete;[11] if these problems were efficiently solvable it could spur considerable advances in biology.

But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook,[12]

...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.

Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated – for instance, Fermat's Last Theorem took over three centuries to prove. A method that is guaranteed to find proofs to theorems, should one exist of a "reasonable" size, would essentially end this struggle.

A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a massive advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.
(EndQuote)

I dont know much about computer science, I was wondering which fields of computer science and mathematics do I have to learn in order to get aquainted with the problem? I by no means would attempt to solve it but im very curious about it because of its vast implications.

Last edited by a moderator: Apr 24, 2017
2. Sep 5, 2009

### Coin

There are two particular branches of theoretical computer science you will need to understand in order to seriously think about the P vs NP problem. The first one is often called "automata theory". The second one is called "complexity theory". The first one will be often taught in a "fundamental computer science" class, although not all learning institutions offer these. Complexity theory can be taught as an extension of basic automata theory, however you will more often see it taught alone-- actually it will be covered in this way in any algorithms class (if you have ever encountered "Big O Notation", this is complexity theory).

If you want to really jump headfirst into this, I suggest Papadimitriou's "Computational Complexity" textbook, which really seems to be the gold standard on the subject.

If you want just an introduction to the subject, I cannot highly enough recommend Scott Aaronson's "Quantum Computing Since Democritus" series. Go to the site I linked there and look on the sidebar for that title, there are transcripts of about 20 lectures listed. The first half will be the ones that will mostly be of interest to you. This series is wide-ranging in subject and its ultimate goal is to introduce you to quantum computing (a subject which not only will be relatable to you if you have a physics background, but also actually does have interesting relevance to the P vs NP problem for several reasons) but on the way to his goal he gives a great, readable introduction to complexity classes and some relevant introduction to automata.

3. Sep 6, 2009

### junglebeast

This would typically be covered in "algorithms / analysis of algorithms." An example course textbook is Kleinberg & Tardos' "Algorithm Design."

4. Sep 14, 2009

### Jimmy84

Thanks a lot guys, I appreciate it.