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. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
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.