The P versus NP Problem (official Millennium Prize problem description)

2 STEPHEN COOK define the class P of languages by P = {L | L = L(M ) for some Turing machine M that runs in polynomial time}. The notation NP stands for “nondeterministic polynomial time”, since originally NP was defined in terms of nondeterministic machines (that is, machines that have more than one possible move from a given configuration). However, now it is customary to give an equivalent definition using the notion of a checking relation, which is simply a binary relation R ⊆ Σ∗ × Σ∗ 1 for some finite alphabets Σ and Σ1. We associate with each such relation R a language LR over Σ ∪ Σ1 ∪ {#} defined by LR = {w#y | R(w, y)} where the symbol # is not in Σ. We say that R is polynomial-time iff LR ∈ P. Now we define the class NP of languages by the condition that a language L over Σ is in NP iff there is k ∈ N and a polynomial-time checking relation R such that for all w ∈ Σ∗, w ∈ L ⇐⇒ ∃y(|y| ≤ |w|k and R(w, y)), where |w| and |y| denote the lengths of w and y, respectively. Problem Statement. Does P = NP? It is easy to see that the answer is independent of the size of the alphabet Σ (we assume |Σ| ≥ 2), since strings over an alphabet of any fixed size can be efficiently coded by strings over a binary alphabet. (For |Σ| = 1 the problem is still open, although it is possible that P = NP in this case but not in the general case.) It is trivial to show that P ⊆ NP, since for each language L over Σ, if L ∈ P then we can define the polynomial-time checking relation R ⊆ Σ∗ ∪ Σ∗ by R(w, y) ⇐⇒ w ∈ L for all w, y ∈ Σ∗. Here are two simple examples, using decimal notation to code natural numbers: The set of perfect squares is in P, since Newton’s method can be used to efficiently approximate square roots. The set of composite numbers is in NP, where (denoting the decimal notation for a natural number c by c) the associated polynomial time checking relation R is given by (1) R(a, b) ⇐⇒ 1 < b < a and b|a. (Recently it was shown that in fact the set of composite numbers is also in P [1], answering a longstanding open question.) 2. History and Importance The importance of the P vs NP question stems from the successful theories of NP-completeness and complexity-based cryptography, as well as the potentially stunning practical consequences of a constructive proof of P = NP. The theory of NP-completeness has its roots in computability theory, which originated in the work of Turing, Church, G¨odel, and others in the 1930s. The computability precursors of the classes P and NP are the classes of decidable and c.e. (computably enumerable) languages, respectively. We say that a language L is c.e. (or semi-decidable) iff L = L(M ) for some Turing machine M . We say that L