What is the P versus NP problem?
The P versus NP problem is a major unsolved question in theoretical computer science asking whether every problem whose solution can be quickly verified can also be quickly solved. Class P represents problems solvable in polynomial time, while class NP represents problems where a proposed solution can be verified in polynomial time. Most computer scientists believe that P is not equal to NP, implying there are problems that are harder to compute than to verify.
What we know
- The P versus NP problem asks whether every decision problem with a quickly verifiable positive answer can also be quickly solved. [2]
- Class P consists of questions that an algorithm can answer in polynomial time, whereas class NP consists of questions where an answer can be verified in polynomial time. [2]
- It is widely believed that P is strictly smaller than NP, meaning some problems in NP cannot be solved in polynomial time. [2, 4]
- The problem is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each carrying a one million dollar prize. [2, 3]
Still open
- Whether P is equal to NP or P is not equal to NP remains unproven.
Where to go next
- a case in pointWhat are NP-complete problems?
- the bigger pictureWhat are the seven Millennium Prize Problems?
- how we knowHow did Richard Karp establish his 21 NP-complete problems?
- what followedHow would resolving P versus NP affect cryptography and artificial intelligence?
- compared withWhat is the relationship between complexity classes NP and co-NP?
- an unexpected connectionHow does the Poincaré conjecture link to other millennium math problems?Both the Poincaré conjecture and the P versus NP problem are part of the exact same elite set of seven Millennium Prize Problems designated in the year 2000.
Sources
- [1]P versus NP problem (Wikidata Q746242) · CC0 1.0
- [2]P versus NP problem · CC BY-SA 4.0
- [3]Millennium Prize Problems · CC BY-SA 4.0
- [4]NP (complexity) · CC BY-SA 4.0
- [5]Karp's 21 NP-complete problems · CC BY-SA 4.0