P = NP

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.

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

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.

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.