P versus NP

Computer science · Computational complexity Millennium Prize Problems

P versus NP

A decision problem is represented by a language $L\subseteq\{0,1\}^*$. The class $\mathrm{P}$ consists of languages decided by a deterministic Turing machine in time polynomial in the input length. The class $\mathrm{NP}$ consists of languages for which membership has polynomial-length certificates checkable by a deterministic polynomial-time verifier: there are a polynomial $q$ and such a verifier $V$ with

Determine whether $\mathrm{P}=\mathrm{NP}$ or $\mathrm{P}\neq\mathrm{NP}$.

For example, a deterministic polynomial-time algorithm for Boolean satisfiability (SAT), with a proof of correctness and a worst-case polynomial running-time bound for all inputs, would establish equality. Proving that SAT has no deterministic polynomial-time algorithm would establish inequality. SAT asks whether a given Boolean formula has a satisfying truth assignment.

Algorithms successful only on selected distributions or finite test sets do not establish equality. Lower bounds for a restricted computational model must be distinguished from a lower bound against all deterministic polynomial-time algorithms. Substantial advances on restricted models, proof barriers or general algorithmic methods are useful when their relationship to the main question is clear.

Source: Clay Mathematics Institute, P vs NP, Millennium Prize Problems.

Type

closed-ended

Solve status

open

Access

Public