P vs NP
P vs NP explained: why verifying solutions is easy but finding them may be hard, what polynomial time means, and why this Millennium Prize problem matters.
The P versus NP question asks whether every problem whose solution can be verified quickly can also be solved quickly. P contains decision problems solvable in polynomial time; NP contains those verifiable in polynomial time. Whether these classes are equal is the most important open problem in theoretical computer science.
Polynomial time and Big-O notation
A problem is in P when some algorithm solves it in time bounded by a polynomial in the input size — n, n squared, n cubed, and so on. Polynomial growth stays manageable as inputs grow, while exponential growth doubles with each added input bit and quickly exceeds any physical budget. The standard vocabulary for these growth rates is Big-O notation, which classifies algorithms by how their running time scales with input size. Sorting, shortest paths, matching, and linear programming are all in P: efficient algorithms exist and run daily at enormous scale. The class P is our formalization of feasible computation, a thesis going back to Cobham and Edmonds in the 1960s.
NP and efficient verification
NP — nondeterministic polynomial time — contains the decision problems whose yes-answers can be checked in polynomial time given the right certificate. A Sudoku solution is hard to find but trivial to verify; so is a claimed route visiting every city under a budget, or a satisfying assignment to a Boolean formula. Every problem in P is automatically in NP, because solving a problem includes verifying a solution, so P is contained in NP. The open question is whether the containment is strict — whether verification-easy truly exceeds solution-easy.
NP-completeness and reductions
Thousands of problems in NP share a remarkable property: each is at least as hard as every other problem in NP. These are the NP-complete problems — satisfiability, the traveling salesman decision problem, graph coloring, knapsack — connected by polynomial-time reductions that translate any NP problem into any one of them. Cook and Levin proved the first completeness result in 1971, and Karp followed with 21 classic problems. A polynomial-time algorithm for any single NP-complete problem would collapse all of NP into P. Coping strategies like dynamic programming solve important special cases efficiently, but they do not settle the general question.
Why P versus NP matters in practice
Modern cryptography assumes P differs from NP: public-key cryptography rests on problems believed hard to solve yet easy to verify, such as factoring large integers. A proof that P equals NP, with a practical algorithm, would break encryption, revolutionize optimization and scheduling, and automate theorem proving and drug design. A proof of inequality would confirm that some verification-easy problems are intrinsically hard to solve. Named a Millennium Prize Problem with a million-dollar bounty, the question has resisted half a century of attack: most experts believe P differs from NP, but belief is not proof.
Tags
algorithms complexity theory computation np-complete
Related articles
- Quantum Computing
- Prime Numbers and the Sieve of Eratosthenes
- Quicksort
- How Dating App Algorithms Actually Work
- Dating App Shadowbans: What They Are and How to Actually Test
- How ATS Resume Screening Actually Works