P versus NP
P is the class of decision problems that can be solved in polynomial time, and NP is the class of decision problems whose yes answers can be checked in polynomial time given a suitable certificate. Is P equal to NP? Equivalently, does some NP-complete problem, such as Boolean satisfiability, have a polynomial-time algorithm?
History and references
Still open as of 2026.
Stephen Cook formalized the question in 1971 and Leonid Levin did so independently by 1973, while Kurt Gödel had asked a version of it in a 1956 letter to John von Neumann. Many natural problems, including satisfiability, graph coloring and the decision version of the traveling salesman problem, are NP-complete, so a polynomial algorithm for any one of them would give one for all of NP. Most researchers believe that P is not equal to NP, and in a 2019 poll 88% of respondents said so. Three known barriers, called relativization, natural proofs and algebrization, show that broad families of proof techniques cannot settle the question. It is one of the seven Clay Millennium Prize Problems.
References
Solutions 0
Sign in or create an account to publish a solution