Open Questions
Does P equal NP?
Citation Formats
General Reference
APA Style
BibTeX
Facts
Why OpenThe 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. 1 What Would ResolveA 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. 1 Discipline NeededComputational complexity theory, Mathematics 1 Question Kind Question Status Open Question
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.
OpenComputational complexity theory, MathematicsWikipedia: P versus NP Problem
Cross-Tradition Connections
Sources
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.