P versus NP problem — 문제 정의 (영어 원문)

Introduction

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

Here, "quickly" means an algorithm exists that solves the task and runs in polynomial time (as opposed to, say, exponential time), meaning the task completion time is bounded above by a polynomial function on the size of the input to the algorithm. The general class of questions that some algorithm can answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if provided with an answer, it can be verified quickly. The class of questions where an answer can be verified in polynomial time is "NP", standing for "nondeterministic polynomial time".

An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

The problem has been called the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for 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 selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.

Example

Consider the following yes/no problem: given an incomplete Sudoku grid of size n² × n², is there at least one legal solution where every row, column, and n × n square contains the integers 1 through n²? It is straightforward to verify "yes" instances of this generalized Sudoku problem given a candidate solution. However, it is not known whether there is a polynomial-time algorithm that can correctly answer "yes" or "no" to all instances of this problem. Therefore, generalized Sudoku is in NP (quickly verifiable), but may or may not be in P (quickly solvable). (It is necessary to consider a generalized version of Sudoku, as any fixed size Sudoku has only a finite number of possible grids. In this case the problem is in P, as the answer can be found by table lookup.)

History — precise statement

The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures", and independently by Leonid Levin in 1973.

Formal definitions — P and NP

A decision problem is a problem that takes as input some string w over an alphabet Σ, and outputs "yes" or "no". If there is an algorithm (say a Turing machine, or a computer program with unbounded memory) that produces the correct answer for any input string of length n in at most c·n^k steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Formally, P is the set of languages that can be decided by a deterministic polynomial-time Turing machine. Meaning,

P = { L : L = L(M) for some deterministic polynomial-time Turing machine M }

where

L(M) = { w ∈ Σ* : M accepts w }

and a deterministic polynomial-time Turing machine is a deterministic Turing machine M that satisfies two conditions:

1. M halts on all inputs w and
2. there exists k ∈ N such that T_M(n) ∈ O(n^k), where O refers to the big O notation and

T_M(n) = max { t_M(w) : w ∈ Σ*, |w| = n }
t_M(w) = number of steps M takes to halt on input w.

NP can be defined similarly using nondeterministic Turing machines (the traditional way). However, a modern approach uses the concept of certificate and verifier. Formally, NP is the set of languages with a finite alphabet and verifier that runs in polynomial time. The following defines a "verifier":

Let L be a language over a finite alphabet, Σ.

L ∈ NP if, and only if, there exists a binary relation R ⊂ Σ* × Σ* and a positive integer k such that the following two conditions are satisfied:

1. For all x ∈ Σ*, x ∈ L ⇔ ∃ y ∈ Σ* such that (x, y) ∈ R and |y| ∈ O(|x|^k); and
2. the language L_R = { x#y : (x, y) ∈ R } over Σ ∪ {#} is decidable by a deterministic Turing machine in polynomial time.

A Turing machine that decides L_R is called a verifier for L and a y such that (x, y) ∈ R is called a certificate of membership of x in L.

Not all verifiers must be polynomial-time. However, for L to be in NP, there must be a verifier that runs in polynomial time.