P vs NP Problem
The P vs NP problem asks whether every problem whose solution can be verified in polynomial time (class NP) can also be solved in polynomial time (class P). It is one of the seven Millennium Prize Problems, carrying a $1,000,000 prize from the Clay Mathematics Institute, and is considered the most important open question in theoretical computer science. If P = NP were proven, it would imply that problems like RSA encryption, protein folding optimisation, and NP-complete combinatorial problems could all be solved efficiently, fundamentally transforming cryptography, artificial intelligence, and computational biology.
Key Complexity Classes in the P vs NP Landscape
| Class | Definition | Verification | Solution | Example Problems |
|---|---|---|---|---|
| P | Solvable in polynomial time | Polynomial | Polynomial | Sorting, shortest path, primality testing |
| NP | Verifiable in polynomial time | Polynomial | Unknown (exp. worst case) | SAT, Hamiltonian path, factoring (maybe) |
| NP-Complete | Hardest problems in NP | Polynomial | Unknown | SAT, TSP, Graph Colouring |
| NP-Hard | At least as hard as NP-complete | Not necessarily poly | Unknown | Halting problem, TSP optimisation |
| co-NP | Complement of NP problems | Polynomial (for "no") | Unknown | TAUTOLOGY, non-Hamiltonicity |
| PSPACE | Solvable in polynomial space | Any | Poly space | QBF, game strategies |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
The complexity classes "P" and "NP" were formally defined in the late 1960s–early 1970s. "P" (Polynomial time) was described by Jack Edmonds and Alan Cobham around 1965. "NP" (Nondeterministic Polynomial time) emerged from Stephen Cook's 1971 paper. The explicit "P vs NP" formulation as an open problem is attributed to Cook's 1971 work and was popularised by Karp's 1972 paper.