P = NP

A hypothesis in theoretical computing science regarding the running time of algorithms.

P refers to PTIME, the class of algorithms that have running time proportional to a polynomial in terms of the input size.

NP refers to NPTIME, the class of nondeterministic algorithms with polynomial running time in terms of the input size.

Stephen A. Cook and others obtained some interesting results in NP problems; in particular, in 1971 he showed that satisfiability is NP-complete. NP-complete problems are the 'hardest' in NP: if a polynomial time deterministic algorithm is found for one of them, it can be adapted to work for any problem in NPTIME. In short, it would prove that P = NP.

30 years on, this is considered immensely unlikely, but no formal refutation of the possibility has yet been found.

Umesh Vazirani's quantum computing work at Berkeley may soon be able to disprove it, though. I believe they're at a stage now where
( P = NP || quantum computers can work exponentially faster than DTMs ).

But I'm ignorant, so don't quote me on that.

(computational complexity):

The most important open problem in the field.

The class P is (trivially) a subset of the class NP. Nondeterminism is always optional. However, it would appear absurd that P=NP. A nondeterministic machine trying to decide membership in a language is presented with a hint (called a "witness" or "certificate") which proves membership (no such witness is provided for elements outside the language; the definition is asymmetric).

So most people would be extremely surprised to discover P=NP. It would also have strong repercussions on the way we think of algorithms. But nobody has any idea how to prove that P!=NP.

To show P!=NP it is sufficient to show that one problem in NP is not in P. To show P=NP, it is sufficient to show that one NP-complete problem (say SAT) is in P (an NP-complete problem is by definition in NP, so if it's not in P then P!=NP). Note that this immediately gives a concrete equivalent question: Does there exist a polynomial-time (deterministic) algorithm for checking boolean formula satisfiability?

More structural approaches have also been tried. For instance, the definition of NP is not symmetric. If we know a language is in NP, we generally do not know that its complement (the set of words not in the language) is in NP. The class of these complements is coNP. But if a language is in P, then so is its complement. So if we could show NP!=coNP, we would immediately deduce that P!=NP (otherwise, since P=coP, NP=P=coP=coNP using some trivial logic). Now, very few problems are known to be both in NP and in coNP, yet not known to be in P. And of course, none of these problems are NP complete (an NP complete problem in coNP would immediately show NP=coNP). Yet proving a language is not in NP (or not in coNP) is also a very difficult task.

Some approaches are known not to work. The usual method for solving problems like the halting problem is known as diagonalization. However, it can be shown that diagonalization isn't strong enough to show P!=NP. In other words, a much better understanding of P will be required to show P!=NP, one from which we are very far.

This is one of the seven Millennium Prize Problems proposed by the Clay Mathematics Institute in April 2000.

The Millennium Problem is that no-one can prove whether or not P is equivalent to NP. To show P is not equivalent to NP would require a complex mathematical proof. To show P is equivalent to NP would just require finding a polynomial algorithm for one particular NP problem. It is known that if one such algorithm existed then it could be adapted to solve any NP problem in polynomial time.

A worrying point is that RSA decryption is an NP problem, and so if it was shown that P=NP, then the world would be thrown into chaos as all RSA privacy would go down. That may happen anyway with the development of quantum computers.

While it is true that the class P is the set of all problems which have an algorithmic solution in polynomial time by a deterministic Turing machine, the class NP is the set of all problems which have an algorithmic solution in polynomial time by a non-deterministic Turing machine.

There are problems which can be solved in exponential time which are not in NP; NP is a proper subset of exponentially solvable problems.

An equivalent description of the class NP is the set of problems whose answers (once gotten from some magic oracle or God or whatever your ontological committments demand) can be verified in polynomial time by a deterministic Turing machine. The Travelling Salesman Problem can be verified in polynomial time (hand me the itinerary, and I can say either "Yes" or "No" very quickly to the question of whether it visits each vertex on a non-complete graph without repetition) by a deterministic Turing machine, but no algorithm has yet been found to solve this problem in polynomial time on a deterministic Turing machine.