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 FAQs
What would happen to cryptography if P equaled NP?
It could break most existing cryptosystems if the solution were constructive and efficient.
A solution showing that P equals NP could upend the field of cryptography, which relies on certain problems being difficult. A constructive and efficient solution to an NP-complete problem such as 3-SAT would break most existing cryptosystems.
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.
Source Wikipedia: NP-completeness
In Field
Source Wikipedia: P versus NP Problem
Open Questions
In the Other Atlases
Same As
Also in Mathematics Atlas: the same subject.
Sources
1. Wikipedia: P versus NP Problem
Wikimedia FoundationIntroduction
The P versus NP problem is a major unsolved problem in theoretical computer science.
History
In a 1956 letter written by Kurt Gödel to John von Neumann, Gödel asked whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time, and posited that if so, then the discovery of mathematical proofs could be automated.
- In Field: Algorithms and Complexity Theory
In Group: Unresolved Problems in Complexity Theory, Lead
The P versus NP problem is a major unsolved problem in theoretical computer science.
View the Source Wikipedia: NP-completeness
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)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.