P, NP & verification

What 'efficient' means, the difference between solving and checking, and the P vs NP question. · 10 min read

From cost to tractability

Big-O told us how an algorithm's cost grows. Complexity theory asks a deeper question: for a given problem, does any efficient algorithm exist at all? "Efficient" is defined as polynomial time — O(nᵏ) for some constant k. Polynomial is the dividing line because polynomials compose and stay manageable, while exponential (2ⁿ, n!) blows up past tiny inputs.

Decision problems

Complexity classes are usually phrased over decision problems — questions with a yes/no answer ("is there a route shorter than L?"). Optimisation problems ("what is the shortest route?") have an equivalent decision form, so this loses no generality.

The class P

P is the set of decision problems solvable in polynomial time. Sorting, shortest paths, matching, linear programming — anything you've written an O(nᵏ) algorithm for lives in P. These are the problems we consider "tractable".

The class NP

NP is the set of problems whose yes-answers can be verified in polynomial time, given a short "certificate" (a proposed solution). You might not be able to find a Sudoku solution quickly, but if someone hands you a filled grid you can check it fast. That's the essence of NP: easy to check, maybe hard to find.

P vs NP

Does P = NP? — i.e., is every problem whose answer is easy to check also easy to solve? It is the most famous open question in computer science (and a \$1M Millennium Prize). Almost everyone believes P ≠ NP: that some problems are genuinely hard to solve even though solutions are easy to verify. Nothing in this chapter depends on the answer — we just work as if P ≠ NP, because no polynomial algorithm is known for the hard problems below.