Concepts
P versus NP
Also Known As P = NP problem
Open Problem
Citation Formats
General Reference
APA Style
BibTeX
P versus NP asks whether every decision problem whose proposed solution can be verified in polynomial time can also be solved in polynomial time: whether complexity class P equals complexity class NP. Stephen Cook's 1971 paper on theorem-proving procedures gave the question its modern formal statement, a result now known as the Cook-Levin theorem after Leonid Levin's independent 1973 formulation in the Soviet Union. It is one of the seven Clay Mathematics Institute Millennium Prize Problems, carrying a one million dollar prize for a correct resolution, and it remains open: no proof that P equals NP, or that it does not, has been accepted by the field. Most computer scientists conjecture that P does not equal NP, though the conjecture itself is unproven.
Facts
Core PrincipleWhether every decision problem whose proposed solution can be verified in polynomial time can also be solved in polynomial time. 1 Cross-Tradition Connections
Associated With
If any NP-complete problem were shown to have a polynomial-time algorithm, every problem in NP would; this is the tightest known link between the two open questions.
In Field
In the Other Atlases
- Also in Mathematics Atlas: P versus NP, the same subject.
Sources
Open Questions (1 open question)
Does P equal NP?
The P versus NP problem is a major unsolved problem in theoretical computer science: it asks whether every decision problem whose proposed positive answer can be quickly verified can also be quickly solved. Stephen Cook introduced its precise statement in 1971, and despite half a century of effort nobody has proved the classes equal or unequal; it is one of the seven Millennium Prize Problems, with a one million dollar prize for the first correct solution.
What would resolve this A proof that every problem in NP admits a polynomial time algorithm, or a proof that some NP problem admits none. Either direction would be among the most consequential results in the history of mathematics and computing.
Computational complexity theory, MathematicsWikipedia: P versus NP Problem
Reader Challenges (0 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.