P versus NP

The P versus NP problem is a central open question in theoretical computer science. It asks, informally, whether any problem whose correct answer can be checked quickly can also be solved quickly. "Quickly" here means that an algorithm exists which completes the task in polynomial time—that is, the time needed grows no faster than a polynomial function of the input size, as opposed to, say, an exponential function. The set of decision problems solvable in polynomial time is called "P" or "class P." For other problems, no fast solution is known, but if a proposed answer is given, it can be verified in polynomial time. This set of problems is called "NP," which stands for "nondeterministic polynomial time."

Resolving P versus NP would reveal whether problems that can be verified in polynomial time can also be solved in polynomial time. If P ≠ NP—which most researchers believe—then some problems in NP are harder to solve than to verify: they cannot be solved in polynomial time, even though their answers can be checked quickly.

This problem is often called the most important open problem in computer science. Beyond its significance in computational theory, a proof either way would deeply affect mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics, and many other fields. It is one of the seven Millennium Prize Problems chosen by the Clay Mathematics Institute, each offering a US$1,000,000 prize for the first correct solution.

**Example** Consider a yes/no problem: given an incomplete \(n^2 \times n^2\) Sudoku grid, is there at least one legal solution where every row, column, and \(n \times n\) square contains the integers 1 through \(n^2\)? For a candidate solution, it is straightforward to verify a "yes" instance. However, no polynomial-time algorithm is known that can correctly answer "yes" or "no" for all instances of this generalized problem. Thus, generalized Sudoku is in NP (quickly verifiable), but it may or may not be in P (quickly solvable). (A fixed-size Sudoku has only finitely many possible grids, so that specific case is in P, as the answer can be found by table lookup.)

**History** The precise formulation of the P versus NP problem was introduced in 1971 by Stephen Cook in his paper "The complexity of theorem proving procedures," and independently by Leonid Levin in 1973. Earlier hints of the underlying issues existed. In 1955, mathematician John Nash wrote to the National Security Agency, suggesting that the time to crack a sufficiently complex code would grow exponentially with key length. If proven, this would imply what is now called P ≠ NP, since a proposed key can be verified in polynomial time. In a 1956 letter from Kurt Gödel to John von Neumann, Gödel asked whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time, and noted that if so, the discovery of mathematical proofs could be automated.

**Context** The relationship between P and NP is studied in computational complexity theory, which examines the resources—most commonly time (number of steps) and space (amount of memory)—required to solve a problem. Such analysis requires a model of the computer. Typically, the model assumes a deterministic machine (given its state and inputs, only one action is possible) that is sequential (it performs actions one after another). In this theory, class P consists of all decision problems solvable on a deterministic sequential machine in time polynomial in the input size. Class NP consists of all decision problems whose positive solutions can be verified in polynomial time given the right information—equivalently, whose solution can be found in polynomial time on a nondeterministic machine. More formally, a language \(L\) is in NP if there exists a relation \(R\) decidable in polynomial time and a polynomial \(p\) such that \(x \in L\) if and only if there exists a \(y\) with \(|y| \leq p(|x|)\) and \(R(x, y)\). In this formulation, P versus NP asks whether polynomial-time decidable predicates are closed under polynomially bounded existential quantification.