The importance of the P versus NP question
Stephen A Cook · Journal of the ACM · 2003
The P versus NP problem is to determine whether every language accepted by some nondeterministic Turing machine in polynomial time is also accepted by some de-terministic Turing machine in polynomial time. Unquestionably this problem has caught the interest of the mathematical community. For example, it is the first of seven million-dollar “Millennium Prize Problems ” listed by the Clay Mathematics Institute [www.claymath.org]. The Riemann Hypothesis and Poincare ́ Conjec-ture, both mathematical classics, are farther down the list. On the other hand, Fields Medalist Steve Smale lists P versus NP as problem number three, after Riemann and Poincaré, in “Mathematical Problems for the Next Century ” [Smale 1998]. But P versus NP is also a problem of central interest in computer science. It was posed thirty years ago [Cook 1971; Levin 1973] as a problem concerned with the fundamental limits of feasible computation. Although this question is front and center in complexity theory, NP-completeness proofs have become pervasive in many other areas of computer science, including artificial intelligence, databases, programming languages, and computer networks (see Garey and Johnson [1979]