Complexity Theory

Complexity classes and P vs NP

Which problems are tractable, and the biggest open question

~13 minLesson 25 of 25Written by Claude Opus 4.8

Some problems are trivial to check yet seem impossibly hard to solve - and after fifty years, nobody can prove they truly are.

Hand someone a completed Sudoku and they can confirm it's correct in seconds - scan every row, column, and box. Hand them a blank one and the work explodes: they may have to try astronomically many fillings before one clicks. That yawning gap between checking a solution and finding one is the whole subject of complexity theory - and the single biggest open question in computer science lives inside it.

Solve vs verify

Two totally different jobs. Solving means producing an answer from scratch. Verifying means: I hand you a candidate answer (a certificate) and you tell me whether it's valid. Complexity classes sort problems by how expensive each job is - and the shock is that for a huge, important family of problems, verifying is cheap while every known way to solve is ruinously expensive.

Two ways to be hard: solving vs checking

We measure cost with Big-O in the input size $n$ . A cost like $n$ , $n^{2}$ , or $n^{3}$ is polynomial - it grows gently and we call such problems tractable. A cost like $2^{n}$ is exponential - it doubles with every extra unit of input and is intractable in practice. Two classes carve up the world:

P - problems solvable in polynomial time. Sorting, binary search, shortest paths (Dijkstra), matrix multiply. These we can actually run.
NP - problems whose proposed solutions are verifiable in polynomial time. Formally, $L \in NP$ when there is a polynomial-time checker $V$ and a polynomial bound $p$ such that

x \in L ⟺ \exists c (∣ c ∣ \leq p (∣ x ∣) and V (x, c) = 1) .

Read $c$ as the certificate - the filled-in Sudoku, the satisfying assignment, the route. NP says: if someone whispers you the right $c$ , you can check it fast. It says nothing about how hard $c$ was to find. Every problem in P is trivially in NP (just re-solve it to check), so $P \subseteq NP$ . The trillion-dollar question is whether that containment is strict.

# VERIFY: given an assignment, is every clause satisfied? - O(m), polynomial
def verify(clauses, assignment):
    for clause in clauses:                 # m clauses
        if not any(assignment[v] ^ neg    # is any literal true?
                   for (v, neg) in clause):
            return False
    return True                            # all satisfied → certificate is valid

# SOLVE: no certificate handed to us - try every assignment - O(2**n * m)
def solve(clauses, n):
    for bits in range(2 ** n):              # 2**n candidates (!)
        a = [(bits >> i) & 1 for i in range(n)]
        if verify(clauses, a):
            return a
    return None                            # unsatisfiable

Verify is a fast subroutine; solve wraps it in an exponential loop

The race: verify in a blink, solve for centuries

Below is a real Boolean satisfiability (SAT) instance: $n$ variables and $m$ clauses, each an OR of three literals. You're handed a certificate - a proposed assignment that happens to satisfy every clause. Press Race: on the left, the verifier checks all $m$ clauses and finishes almost instantly. On the right, a solver with no certificate must brute-force the space of $2^{n}$ assignments. Now drag $n$ upward and watch the right side fall off a cliff.

SAT - verify a certificate vs brute-force solve. Drag n, then press Race.

variables n = 42clauses m = 168

certificate (a proposed assignment):110011111001011110100000001100001101100011

(x12 ∨ ¬x27 ∨ ¬x2) ∧ (¬x26 ∨ x29 ∨ x27) ∧ (¬x7 ∨ ¬x21 ∨ x42) ∧ … - 168 clauses total

① Verify the certificate

check each clause once - m operations, polynomial

ops: 0 / 168verify ≈ 168 ns

② Solve from scratch

no certificate - try assignments, up to 2ⁿ

tried: 0 / 2ⁿ = 4.40 × 10¹²explored: 0%

Full 2ⁿ search would take ≈ 8.6 days. Press Race.

At n = 42: verifying tests m = 168 clauses; solving tests up to 2ⁿ = 4.40 × 10¹² assignments - a gap of exactly 2ⁿ, even at a billion checks per second.

The gap is exactly 2ⁿ - and that asymmetry is for sale

The arithmetic is clean: verifying costs

m

clause-checks, solving by brute force costs

2^{n}

of those same checks. Their ratio is exactly

2^{n}

- solving does

2^{n}

times the work of checking, no matter the machine. That one-way cheapness is precisely what cryptography sells: a signature or a decryption is easy to verify but believed astronomically hard to forge. If solving ever became as easy as checking, that market - and most of modern security - would evaporate overnight.

The map: P, NP, NP-complete, NP-hard

Inside NP sits a spine of the hardest problems, tied together by reductions. We write $A \leq_{p} B$ (" $A$ reduces to $B$ ") when any instance of $A$ can be rewritten, in polynomial time, as an instance of $B$ - so a fast solver for $B$ instantly becomes a fast solver for $A$ . Reductions let one problem inherit another's hardness.

NP-hard - at least as hard as every problem in NP (everything in NP reduces to it). It need not itself be in NP.
NP-complete - the sweet, terrifying spot: in NP and NP-hard. These are the hardest problems that still have fast verifiers. Crack one in polynomial time and you crack them all.

Class	Solve fast?	Check fast?	Examples
P	yes	yes	binary search, Dijkstra, sorting
NP	unknown	yes	SAT, graph coloring, subset-sum
NP-complete	no known way	yes	3-SAT, Hamiltonian cycle, knapsack
NP-hard	no known way	not necessarily	TSP optimization, halting problem

The keystone is the Cook-Levin theorem (Stephen Cook 1971, Leonid Levin independently): SAT is NP-complete - every problem in NP reduces to it. That's why SAT is the demo's star: it is the universal NP problem, and a polynomial-time SAT solver would collapse all of NP into P. Because thousands of practical problems - scheduling, routing, protein folding, chip layout - are NP-complete, they all stand or fall together. Almost every expert believes $P \neq = NP$ (checking really is easier than solving), but no one has proved it. It is one of the Clay Institute's Millennium Prize Problems, with a one-million-dollar bounty and a half-century of failed attempts.

Check yourself

NP is exactly the set of problems whose proposed solutions can be:

Modern cryptography works because some problems are believed to be:

Recall: what precisely does P vs NP ask?

Try to state it, then check.

Lock it in

P is the class of problems solvable in polynomial time; NP is the class whose proposed solutions are verifiable in polynomial time. $P \subseteq NP$ , and whether that containment is strict is the open question.
The gap between checking a certificate and finding one is the whole subject: for NP-complete problems verifying is cheap while every known solver is exponential.
SAT is NP-complete (Cook-Levin): every NP problem reduces to it, so a polynomial-time SAT solver would collapse all of NP into P.
Cryptography sells exactly that one-way asymmetry - easy to verify, believed hard to forge. Nearly everyone believes $P \neq = NP$ , but no one has proved it.

Primary source

The MIT 6.006 - Introduction to Algorithms lectures cover complexity classes and the P vs NP frontier with rigor. For the official problem statement and its one-million-dollar prize, see the Clay Mathematics Institute - P vs NP Millennium Problem.

Ask your teacher

Want to see a concrete reduction - say, 3-SAT to graph 3-coloring - or how approximation and randomization sidestep NP-hardness in practice? Ask and I'll build the follow-up. This lesson caps the DSA path: backtracking and brute force explode because these problems are (probably) intractable - that's the same wall you hit earlier. And it's the reason cryptography exists at all: some things are easy to verify yet believed genuinely hard to solve.