Computational Complexity Basics

Before we can ask what a quantum computer buys us, we need the vocabulary of classical complexity theory: the precise way computer scientists measure "how hard" a problem is and compare problems to one another. This lesson reviews the asymptotic worst-case framework, the central classes $\mathsf{P}$ and $\mathsf{NP}$ , and the notion of a reduction that organizes problems by difficulty.

Decision problems and resource scaling

Complexity theory is cleanest for decision problems — questions with a yes/no answer, identified with a language $L \subseteq \{0,1\}^*$ , the set of inputs whose answer is "yes." We measure the resources a machine uses (time = number of steps, space = memory cells) as a function of the input length $n$ , and we care about worst-case asymptotics: how the resource grows as $n \to \infty$ , up to constant factors and lower-order terms. The relevant dividing line is polynomial versus superpolynomial. A running time $O(n^c)$ for some fixed constant $c$ is "efficient"; a time like $2^{\,n}$ or $n^{\log n}$ is not.

This focus on polynomials is deliberate. Polynomials are closed under addition, multiplication, and composition, so "efficient" is robust: chaining a polynomial number of polynomial-time subroutines is still polynomial. It also makes the theory machine-independent — the strong Church–Turing thesis asserts that any two reasonable classical models simulate each other with only polynomial overhead, so "polynomial time" means the same thing on a Turing machine, a RAM, or a C program.

The class P

\mathsf{P} = \{\, L : L \text{ is decided by a deterministic Turing machine in time } O(n^c) \text{ for some } c \,\}.

$\mathsf{P}$ is the canonical formalization of tractable. Sorting, shortest paths, linear programming, and primality testing all live in $\mathsf{P}$ . A problem in $\mathsf{P}$ has an algorithm that, on every input, halts with the correct answer after a polynomial number of steps.

The class NP

$\mathsf{NP}$ is the class of decision problems whose yes-instances admit a short, efficiently checkable certificate. Formally, $L \in \mathsf{NP}$ if there is a polynomial-time verifier $V$ and a polynomial $p$ such that

x \in L \iff \exists\, w \in \{0,1\}^{\le p(|x|)} \text{ with } V(x, w) = 1 .

The string $w$ is a witness or proof. For Boolean satisfiability ( $\mathsf{SAT}$ ), the witness is a satisfying assignment, and checking it is trivial. For graph 3-colouring, the witness is the colouring. The defining asymmetry: finding $w$ may be astronomically hard, but verifying a claimed $w$ is easy.

Reductions and completeness

To compare two problems we use a reduction. A polynomial-time many-one reduction from $A$ to $B$ , written $A \le_p B$ , is a polynomial-time computable map $f$ such that

x \in A \iff f(x) \in B .

If such an $f$ exists, then $B$ is "at least as hard" as $A$ : any efficient algorithm for $B$ yields one for $A$ by first running $f$ . Reductions impose a partial order of difficulty on problems.

A problem $B$ is $\mathsf{NP}$ -hard if every $A \in \mathsf{NP}$ reduces to it, and $\mathsf{NP}$ -complete if it is both $\mathsf{NP}$ -hard and itself in $\mathsf{NP}$ . The Cook–Levin theorem established the first $\mathsf{NP}$ -complete problem, $\mathsf{SAT}$ ; thousands more (3-colouring, Hamiltonian cycle, subset-sum, …) followed by reduction from it. $\mathsf{NP}$ -complete problems are the hardest problems in $\mathsf{NP}$ : an efficient algorithm for any one of them would collapse $\mathsf{P} = \mathsf{NP}$ .

Beyond P and NP

Two more classes recur throughout this module. $\mathsf{BPP}$ (bounded-error probabilistic polynomial time) allows the machine to flip fair coins and to err with probability at most $1/3$ on every input; it is the realistic classical notion of "efficient" once randomness is permitted. $\mathsf{PSPACE}$ is everything decidable with a polynomial amount of memory, regardless of time. The standard, widely believed inclusions are

\mathsf{P} \subseteq \mathsf{BPP} \subseteq \ \cdots\ \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXP},

with $\mathsf{NP} \subseteq \mathsf{PSPACE}$ as well. Almost all of these inclusions are not known to be strict: separating them is exactly the hard open territory of the field.

What to carry forward

Three ideas anchor the rest of this module. First, polynomial time is the threshold of efficiency, and it is robust across machine models. Second, $\mathsf{NP}$ is about verification, not solution — short checkable proofs. Third, reductions and completeness let us name the hardest problems in a class without solving them. The quantum classes $\mathsf{BQP}$ and $\mathsf{QMA}$ we meet next are the quantum analogues of $\mathsf{BPP}$ and $\mathsf{NP}$ , built on exactly this scaffolding.