P, NP, and NP-completeness
Some problems seem to resist every efficient algorithm. Complexity theory classifies them and explains why finding a fast algorithm for one would solve thousands of others.
Tractable and intractable
Problems solvable in polynomial time, O(n^k) for some constant k, are considered tractable. Those requiring exponential time, such as 2^n, quickly become impossible: 2^100 steps would take longer than the age of the universe on any computer. Complexity theory asks which problems have polynomial algorithms.
The classes P and NP
P is the class of decision problems, with yes-or-no answers, solvable in polynomial time, such as 'is there a path from s to t?'. NP is the class whose yes-answers can be verified in polynomial time given a certificate: a proposed solution. For Sudoku, checking a filled grid is fast even if finding one seems hard. Every problem in P is in NP.
Reductions
A polynomial-time reduction transforms instances of problem A into instances of problem B so that answers match. If A reduces to B and B has a fast algorithm, so does A; equivalently, if A is hard, B is at least as hard. Reductions are the main tool for comparing problem difficulty.
NP-completeness
A problem is NP-hard if every NP problem reduces to it, and NP-complete if it is also in NP. The Cook-Levin theorem, proved by Stephen Cook in 1971 and independently by Leonid Levin, showed that Boolean satisfiability (SAT) is NP-complete. In 1972, Richard Karp showed 21 more classic problems NP-complete, and thousands are now known.
Famous NP-complete problems
Examples include SAT and 3-SAT; the decision versions of the travelling salesperson problem, 0/1 knapsack, and graph colouring with three or more colours; finding a clique or vertex cover of a given size; Hamiltonian cycle, a cycle visiting every vertex once; subset sum; and generalised Sudoku. Some similar-looking problems are easy: shortest paths, 2-colouring, and Eulerian paths, using every edge once, are all in P.
P versus NP
Whether P equals NP is the most famous open question in computer science and one of the seven Clay Mathematics Institute Millennium Prize Problems, each worth one million dollars. Most researchers believe P is not equal to NP. If it were equal, many hard search problems would become easy, and much of modern cryptography would be at risk.
What to do about hard problems
Proving a problem NP-complete changes your strategy, not your job. Options include: exact algorithms for small inputs, such as DP or branch and bound; special cases that are easier, such as trees or bounded parameters; approximation algorithms with guaranteed quality; heuristics and local search; and powerful general solvers for SAT and integer programming, which routinely solve industrial instances with millions of variables.
Worked example
Vertex cover asks for a set of k vertices touching every edge. Given a proposed set, checking it is easy: scan every edge and confirm at least one endpoint is in the set, O(m), so the problem is in NP. A graph has an independent set of size k exactly when it has a vertex cover of size n - k, since the complement of an independent set covers every edge. This simple reduction shows the two problems are equally hard.
Key takeaways
Polynomial-time problems are tractable; exponential growth quickly becomes infeasible. P contains decision problems solvable in polynomial time; NP contains those whose solutions are verifiable in polynomial time; P is inside NP. Reductions compare difficulty. NP-complete problems are the hardest in NP: Cook-Levin (1971) proved SAT NP-complete, and Karp (1972) added 21 more. TSP, knapsack, colouring, clique, and Hamiltonian cycle are NP-complete, while shortest paths and Eulerian paths are in P. P versus NP is a million-dollar open problem. Hard problems call for small exact methods, special cases, approximation, heuristics, or solvers.
Flashcard
Solvable in polynomial time
Check your understanding
If someone found a polynomial-time algorithm for one NP-complete problem, what would follow?