# Complexity Classes > An algorithm being *possible* is the cheap part — the previous lesson settled that. The expensive > part is *how the cost grows*. Complexity theory sorts decision problems into classes by the > resources (time, space, randomness) a machine needs, and then asks which classes are equal. Almost > every interesting equality is **open** — including the one ($\mathrm P \overset?= \mathrm{NP}$) that > a million-dollar prize rides on. We build the map carefully, because the quantum class > $\mathrm{BQP}$ will have to find its place on it. ## Learning Objectives By the end of this lesson you will be able to: 1. **Use** asymptotic notation ($O, \Omega, \Theta, o, \omega$) precisely and state the definitions. 2. **Formalize** a computational problem as a **decision problem / language** and explain why this loses no generality. 3. **Define** $\mathrm P$, $\mathrm{NP}$, $\mathrm{coNP}$, $\mathrm{BPP}$, and $\mathrm{PSPACE}$ via the Turing-machine model, and state the standard inclusions. 4. **Define** polynomial-time reductions and **NP-completeness**, and explain the role of SAT / 3-SAT (Cook–Levin). 5. **State** clearly what is known and what is open (notably $\mathrm P\overset?=\mathrm{NP}$), and **locate** the question "where does quantum fit?" relative to these classes. --- ## Intuition Two problems can both be "solvable" yet live in entirely different universes of practicality. Sorting $n$ numbers takes $\sim n\log n$ steps — double the input, the work barely more than doubles. Brute-forcing a length-$n$ password over an alphabet of size $k$ takes $\sim k^n$ — add one character, multiply the work by $k$. The first is **polynomial**, the second **exponential**, and that single dichotomy — *polynomial vs. exponential* — is the coarse but astonishingly durable line between "tractable" and "intractable." Three resources matter: - **Time** — number of steps. The class $\mathrm P$ = polynomial time = "efficient." - **Nondeterminism / verification** — can you *check* a claimed solution fast even if *finding* it is hard? That is $\mathrm{NP}$: easy to verify, maybe hard to find. - **Space** — memory cells used. $\mathrm{PSPACE}$ allows polynomial memory but possibly exponential time; you can *reuse* memory, which is why it contains so much. A fourth resource, **randomness**, gives $\mathrm{BPP}$ (efficient with coin flips and a bounded error probability). It is the *classical* benchmark against which quantum's $\mathrm{BQP}$ is measured: a quantum speedup only "counts" if it beats randomized classical algorithms, not just deterministic ones. Hold one picture in mind for the whole lesson — the inclusion chain we will justify: $$ \mathrm P \;\subseteq\; \mathrm{BPP} \;\subseteq\; \mathrm{BQP} \;\subseteq\; \mathrm{PSPACE}, \qquad \mathrm P \;\subseteq\; \mathrm{NP} \;\subseteq\; \mathrm{PSPACE}. $$ Almost none of these inclusions is known to be strict, and where $\mathrm{NP}$ sits relative to $\mathrm{BQP}$ is a central open question. Quantum lives *inside* $\mathrm{PSPACE}$ — it is not magic — but is conjectured to escape $\mathrm{BPP}$. --- ## Theory ### 1. Asymptotic notation (refresher) We measure cost as a function of input size $n$, ignoring constants and low-order terms. For eventually-nonnegative $f, g : \mathbb N \to \mathbb R_{\ge 0}$ [Sip §7.1], [AB §0.3]: | Notation | Definition | Reading | |---|---|---| | $f = O(g)$ | $\exists\,c>0,\,n_0:\ \forall n\ge n_0,\ f(n) \le c\,g(n)$ | $f$ grows **no faster** than $g$ (upper bound) | | $f = \Omega(g)$ | $\exists\,c>0,\,n_0:\ \forall n\ge n_0,\ f(n) \ge c\,g(n)$ | $f$ grows **at least** as fast as $g$ (lower bound) | | $f = \Theta(g)$ | $f = O(g)$ **and** $f = \Omega(g)$ | $f$ and $g$ grow at the **same** rate | | $f = o(g)$ | $\forall\,c>0,\,\exists\,n_0:\ \forall n\ge n_0,\ f(n) < c\,g(n)$ | $f$ is **strictly dominated**: $f/g \to 0$ | | $f = \omega(g)$ | $\forall\,c>0,\,\exists\,n_0:\ \forall n\ge n_0,\ f(n) > c\,g(n)$ | $f$ **strictly dominates**: $f/g \to \infty$ | Useful facts: any polynomial $\sum_{k\le d} a_k n^k$ is $\Theta(n^d)$; logs beat polynomials beat exponentials, $\log n = o(n^\varepsilon) = o(2^n)$ for any $\varepsilon>0$; and $O,\Omega,\Theta$ are *transitive*. The "$=$" here is a traditional abuse — "$f = O(g)$" means "$f \in O(g)$," set membership, not equality. > **Why polynomials are the dividing line.** Polynomials are closed under addition, multiplication, > and composition. That closure is exactly what makes $\mathrm P$ robust: composing two > polynomial-time subroutines, or simulating one polynomial model on another with polynomial overhead > (the Extended Church–Turing thesis from > [Lesson 1](01-models-of-computation.md#4-the-churchturing-thesis-and-its-extended-form)), keeps you > in polynomial time. Exponentials are not so forgiving. ### 2. Decision problems and languages A **decision problem** asks a yes/no question of an input. We encode inputs as strings over $\Sigma=\{0,1\}$ and identify the problem with its **language** — the set of yes-instances: $$ L \;=\; \{\, x \in \{0,1\}^* : \text{the answer on } x \text{ is "yes"} \,\}. $$ For example $\mathrm{PRIMES} = \{\, \langle p\rangle : p \text{ is prime}\,\}$, where $\langle\cdot\rangle$ denotes a binary encoding. "Deciding $L$" means a TM that halts on every input and accepts exactly $L$ (Lesson 1). This costs no generality. A *search* problem ("output a satisfying assignment") or *optimization* problem ("find the largest clique") reduces to polynomially many decision queries by **binary search / self-reduction**: e.g. ask "is the max clique $\ge k$?" for each $k$, then fix vertices one at a time. So classifying *languages* by difficulty classifies *all* of computation, and lets us use the clean machine-decides-a-language framework. ### 3. The class P $$ \mathrm P \;=\; \bigcup_{c \ge 1}\ \mathrm{TIME}\!\left(n^c\right), \qquad \mathrm{TIME}(t(n)) = \{\, L : L \text{ is decided by some DTM in } O(t(n)) \text{ time}\,\}. $$ $\mathrm P$ is the class of problems a deterministic TM solves in **polynomial time**. By the Extended Church–Turing thesis it is *machine-independent*: multi-tape TMs, RAM machines, and your laptop all agree on $\mathrm P$. Examples: sorting, shortest paths, linear programming, and — famously — primality testing ($\mathrm{PRIMES}\in\mathrm P$, Agrawal–Kayal–Saxena 2002). $\mathrm P$ is our formal stand-in for "efficiently solvable." ### 4. The class NP, verifiers, and certificates $\mathrm{NP}$ ("nondeterministic polynomial time") is most cleanly defined by **efficient verification** [AB §2.1], [Sip §7.3]: > A language $L \in \mathrm{NP}$ iff there is a polynomial $p$ and a polynomial-time DTM $V$ (the > **verifier**) such that for all $x$, > $$ > x \in L \iff \exists\, u \in \{0,1\}^{p(|x|)} \ \text{ with } \ V(x,u) = 1. > $$ The string $u$ is a **certificate** (or witness). The point: *finding* $u$ may be hard, but *checking* a proposed $u$ is polynomial. Equivalently, $\mathrm{NP}$ is what a **nondeterministic** TM decides in polynomial time — the machine "guesses" $u$ and verifies it. Examples: **SAT** (does a Boolean formula have a satisfying assignment? — certificate: the assignment); **CLIQUE** (does a graph have a $k$-clique? — certificate: the $k$ vertices); **HAMPATH**, **SUBSET-SUM**, integer **factoring as a decision problem**. Each yes-instance has a short, checkable proof. Clearly $\mathrm P \subseteq \mathrm{NP}$: if you can *solve* in polynomial time, you can *verify* by ignoring the certificate and re-solving. The converse — is verifying-easy the same as solving-easy? — is the $\mathrm P$ vs. $\mathrm{NP}$ question. ### 5. co-NP $\mathrm{coNP}$ is the class of languages whose **complements** are in $\mathrm{NP}$: $L\in\mathrm{coNP}\iff \overline L\in\mathrm{NP}$. Where $\mathrm{NP}$ has short proofs of *yes*, $\mathrm{coNP}$ has short proofs of *no*. **TAUTOLOGY** ("is this formula true under *every* assignment?") is the canonical $\mathrm{coNP}$ problem: a *no*-instance has a short certificate (a falsifying assignment), but it is not obvious how to certify *yes* succinctly. We have $\mathrm P \subseteq \mathrm{NP} \cap \mathrm{coNP}$, and whether $\mathrm{NP}=\mathrm{coNP}$ is open (believed false). If $\mathrm{NP}\ne\mathrm{coNP}$ then $\mathrm P\ne\mathrm{NP}$. ### 6. Reductions and NP-completeness A **polynomial-time many-one reduction** from $A$ to $B$, written $A \le_p B$, is a polynomial-time computable map $f$ with $$ x \in A \iff f(x) \in B . $$ Intuition: $f$ rewrites a question about $A$ into an equivalent question about $B$, cheaply. The payoff is *transfer of difficulty*: if $A \le_p B$ and $B \in \mathrm P$, then $A \in \mathrm P$ (run $f$, then the fast algorithm for $B$). Reductions are transitive. $B$ is **NP-hard** if every $A \in \mathrm{NP}$ satisfies $A \le_p B$ ("at least as hard as all of $\mathrm{NP}$"). $B$ is **NP-complete** if it is NP-hard *and* $B \in \mathrm{NP}$ — the hardest problems *inside* $\mathrm{NP}$. The decisive consequence: > If **any** NP-complete problem is in $\mathrm P$, then $\mathrm P = \mathrm{NP}$ — all of > $\mathrm{NP}$ collapses to polynomial time. #### Cook–Levin and SAT / 3-SAT The **Cook–Levin theorem** [AB §2.3], [Sip §7.4] proves that **SAT** (satisfiability of Boolean formulas in CNF) is NP-complete: the polynomial-time computation of *any* $\mathrm{NP}$ verifier on $(x,u)$ can be encoded as a CNF formula that is satisfiable iff a valid certificate $u$ exists. That single theorem bootstraps the entire NP-complete universe — once SAT is complete, you show a new problem $B$ is NP-complete by reducing a *known* complete problem to it: $\mathrm{SAT}\le_p B$. **3-SAT** (CNF with exactly 3 literals per clause) is also NP-complete via a clause-splitting reduction $\mathrm{SAT}\le_p 3\text{-}\mathrm{SAT}$: a long clause $(\ell_1\lor\cdots\lor\ell_k)$ is replaced by a chain of 3-literal clauses linked by fresh variables $z_i$, $$ (\ell_1\lor\ell_2\lor z_1)\ \land\ (\lnot z_1\lor\ell_3\lor z_2)\ \land\ \cdots\ \land\ (\lnot z_{k-3}\lor\ell_{k-1}\lor\ell_k), $$ which is satisfiable (by some setting of the $z_i$) **iff** at least one original literal $\ell_j$ is true. The reduction is polynomial and preserves satisfiability — the template for thousands of NP- completeness proofs (Karp's 21 problems, and onward). ### 7. Randomized computation: BPP Allow the machine fair coin flips. $\mathrm{BPP}$ (**Bounded-error Probabilistic Polynomial time**) is the class of $L$ for which a polynomial-time probabilistic TM $M$ satisfies [AB §7.1] $$ x \in L \ \Rightarrow\ \Pr[M(x)=1] \ge \tfrac23, \qquad x \notin L \ \Rightarrow\ \Pr[M(x)=1] \le \tfrac13 . $$ The constants $\tfrac23,\tfrac13$ are not special: by running $M$ independently $k$ times and taking the **majority vote**, the error drops to $2^{-\Omega(k)}$ (a Chernoff bound), so any gap bounded away from $\tfrac12$ amplifies to near-certainty with polynomially many repetitions. Thus $\mathrm{BPP}$ errors are a non-issue in practice. $\mathrm P \subseteq \mathrm{BPP}$ trivially (ignore the coins). Whether the inclusion is *strict* is open; in fact it is widely conjectured that $\mathrm{P}=\mathrm{BPP}$ (derandomization, under standard hardness assumptions). $\mathrm{BPP}$ is the right *classical* yardstick for quantum speedup: $\mathrm{BQP}$ is the quantum analogue of $\mathrm{BPP}$, and the interesting claim is $\mathrm{BPP}\subsetneq\mathrm{BQP}$. ### 8. Space: PSPACE $$ \mathrm{PSPACE} \;=\; \bigcup_{c \ge 1}\ \mathrm{SPACE}\!\left(n^c\right), $$ problems decidable using **polynomial memory**, with no time bound. Reusing memory is powerful: $\mathrm{PSPACE}$ contains all of $\mathrm{NP}$ (and $\mathrm{coNP}$). To see $\mathrm{NP}\subseteq \mathrm{PSPACE}$, deterministically enumerate every candidate certificate $u\in\{0,1\}^{p(n)}$, running the verifier on each, **reusing** the same $p(n)$ cells — exponential *time*, but polynomial *space*. The canonical $\mathrm{PSPACE}$-complete problem is **TQBF** (true quantified Boolean formulas, $\forall\exists\cdots$). The inclusions $\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$ hold; whether *any* is strict is open, though $\mathrm P\ne\mathrm{PSPACE}$ is strongly believed. ### 9. The map, and what is (not) known Putting it together, with $\subseteq$ proven and $\overset?=$ open: $$ \mathrm P \ \subseteq\ \mathrm{NP},\,\mathrm{coNP} \ \subseteq\ \mathrm{PSPACE}, \qquad \mathrm P \ \subseteq\ \mathrm{BPP} \ \subseteq\ \mathrm{BQP} \ \subseteq\ \mathrm{PSPACE}. $$ | Inclusion | Status | |---|---| | $\mathrm P \subseteq \mathrm{NP}$ | proven $\subseteq$; **strictness open** ($\mathrm P\overset?=\mathrm{NP}$, Clay Millennium Prize) | | $\mathrm P \subseteq \mathrm{BPP}$ | proven; conjectured **equal** (derandomization) | | $\mathrm{BPP}\subseteq\mathrm{BQP}$ | proven; conjectured **strict** (Shor) | | $\mathrm{BQP}\subseteq\mathrm{PSPACE}$ | **proven** (a classical machine can sum amplitudes in poly space) | | $\mathrm{NP}$ vs. $\mathrm{BQP}$ | **incomparable as far as anyone knows**; $\mathrm{NP}\subseteq\mathrm{BQP}$ is *not* believed | Two cultural points worth internalizing. First, almost everything here is **open**: we cannot even *prove* $\mathrm P\ne\mathrm{PSPACE}$, despite overwhelming belief. Second — a common misconception — quantum computers are **not** believed to solve NP-complete problems efficiently. Grover's algorithm (Term 3.2) gives only a *quadratic* speedup for unstructured search, $O(2^{n/2})$, which is provably optimal for the black-box model — far from polynomial. Quantum's exponential wins (Shor) attach to *structured* problems like factoring that are **not** known to be NP-complete. > **Where does quantum fit?** $\mathrm{BQP}$ sits between $\mathrm{BPP}$ and $\mathrm{PSPACE}$. The > central conjectures are $\mathrm{BPP}\subsetneq\mathrm{BQP}$ (quantum genuinely helps) and > $\mathrm{NP}\not\subseteq\mathrm{BQP}$ (it does not help on the hardest verification problems). The > full development — the definition of $\mathrm{BQP}$, the $\mathrm{BQP}\subseteq\mathrm{PSPACE}$ > proof, and the landscape — is > [Term 3.6 · BQP & Quantum Complexity](../../term-3-algorithms/c06-complexity/01-bqp-quantum-complexity.md). --- ## Worked Examples ### Example 1 — A reduction: 3-SAT $\le_p$ INDEPENDENT-SET We show the *technique* of a reduction by transforming a 3-CNF formula $\varphi$ into a graph $G$ and a target $k$ so that $\varphi$ is satisfiable iff $G$ has an independent set of size $k$ (an independent set = vertices, no two adjacent). **Construction.** For each clause $C_j = (\ell_{j1}\lor\ell_{j2}\lor\ell_{j3})$ create a *triangle* of three vertices, one per literal. Add edges **(i)** inside each triangle (so an independent set picks $\le 1$ literal per clause), and **(ii)** between any two vertices labeling *contradictory* literals $x$ and $\lnot x$ (so we never select both a variable and its negation). Set $k = $ number of clauses. **Correctness.** An independent set of size $k$ must take exactly one vertex per triangle (it can take at most one, and needs $k$ total from $k$ triangles) — i.e. one *true* literal per clause — and the contradiction edges guarantee these choices are consistent, defining a satisfying assignment. Conversely a satisfying assignment picks one true literal per clause, and those vertices form an independent set of size $k$. The map is computable in polynomial time (size $O(|\varphi|)$). Hence $3\text{-}\mathrm{SAT}\le_p \mathrm{IND\text{-}SET}$, so INDEPENDENT-SET is NP-hard; since it is also in $\mathrm{NP}$ (certificate = the vertex set), it is **NP-complete**. $\square$ ### Example 2 — Verifier vs. solver: factoring's exponential gap Consider $\mathrm{FACTOR}$-decision: "given $N$ and a bound $B$, does $N$ have a prime factor $\le B$?" The input size is $n = \lceil \log_2 N\rceil$ bits. - **Verification is easy:** a certificate is a factor $d$ with $1= 1) def satisfies(formula, assignment): """VERIFIER: O(size) check that `assignment` (dict var->bool) sat's formula.""" for clause in formula: if not any(assignment[abs(l)] == (l > 0) for l in clause): return False # clause unsatisfied -> formula false return True def brute_force_sat(formula, n_vars): """SOLVER: try all 2**n_vars assignments. Exponential by construction.""" for bits in product((False, True), repeat=n_vars): # 2**n_vars rows assignment = {i + 1: bits[i] for i in range(n_vars)} if satisfies(formula, assignment): return assignment return None # UNSAT # A satisfiable 3-CNF: (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ x3) phi = [[1, 2, -3], [-1, 2, 3], [1, -2, 3]] sol = brute_force_sat(phi, n_vars=3) print("Satisfying assignment:", sol) print("Verifier agrees:", satisfies(phi, sol)) # Watch the search space double per added variable. print("\nSearch-space size 2**v as v grows (the exponential wall):") for v in (10, 15, 20, 22): # A trivially-UNSAT formula forces examining all 2**v rows. unsat = [[1], [-1]] # x1 AND NOT x1 -> always UNSAT t0 = time.perf_counter() brute_force_sat(unsat, n_vars=v) dt = time.perf_counter() - t0 print(f" v={v:2d}: 2**v = {2**v:>10,} brute-force time ≈ {dt*1e3:7.1f} ms") # --------------------------------------------------------------------------- # Reduction demo: 3-SAT -> INDEPENDENT-SET (Example 1). # Build the graph, brute-force the independent set, compare to SAT answer. # --------------------------------------------------------------------------- def reduce_3sat_to_indset(formula): """Return (vertices, edges, k). Vertex = (clause_index, literal).""" vertices = [(j, lit) for j, clause in enumerate(formula) for lit in clause] edges = set() for a in range(len(vertices)): for b in range(a + 1, len(vertices)): (cj, la), (ck, lb) = vertices[a], vertices[b] same_triangle = (cj == ck) # (i) one literal per clause contradictory = (la == -lb) # (ii) consistency edges if same_triangle or contradictory: edges.add((a, b)) return vertices, edges, len(formula) # k = #clauses def has_independent_set(vertices, edges, k): """Brute-force: is there a k-subset with no internal edge?""" from itertools import combinations for subset in combinations(range(len(vertices)), k): s = set(subset) if not any(a in s and b in s for (a, b) in edges): return True return False V, E, k = reduce_3sat_to_indset(phi) sat_answer = brute_force_sat(phi, 3) is not None ind_answer = has_independent_set(V, E, k) print(f"\nReduction check: SAT={sat_answer}, INDEPENDENT-SET(k={k})={ind_answer}") assert sat_answer == ind_answer, "Reduction must preserve the yes/no answer!" print("3-SAT and its reduced INDEPENDENT-SET instance agree. ✓") ``` Expected output (timings are machine-dependent, but the *doubling* is the lesson): ``` Satisfying assignment: {1: False, 2: False, 3: False} # the first one found Verifier agrees: True Search-space size 2**v as v grows (the exponential wall): v=10: 2**v = 1,024 brute-force time ≈ 1.0 ms v=15: 2**v = 32,768 brute-force time ≈ 38.0 ms v=20: 2**v = 1,048,576 brute-force time ≈ 1340.0 ms v=22: 2**v = 4,194,304 brute-force time ≈ 5980.0 ms Reduction check: SAT=True, INDEPENDENT-SET(k=3)=True 3-SAT and its reduced INDEPENDENT-SET instance agree. ✓ ``` Each added variable roughly **doubles** the brute-force time — the exponential wall, live. No known algorithm avoids it in the worst case; whether one *exists* is $\mathrm P\overset?=\mathrm{NP}$. --- ## Exercises **1. (Easy) Asymptotics drill.** Rank by growth rate (slowest first) and give the $\Theta$ class of each: $\;100n,\ \ n\log_2 n,\ \ 2^{10}n^2,\ \ n^{2.5},\ \ 2^{\sqrt n},\ \ 2^{n}/n.$
Solution Order: $100n\ (\Theta(n)) \prec n\log_2 n\ (\Theta(n\log n)) \prec 2^{10}n^2\ (\Theta(n^2)) \prec n^{2.5}\ (\Theta(n^{2.5})) \prec 2^{\sqrt n}\ (\text{sub-exponential}) \prec 2^n/n$. Constants ($100$, $2^{10}$) vanish inside $\Theta$. Note $2^{\sqrt n}$ beats every polynomial ($\sqrt n\,\log 2 = \omega(\log n)$) but is dominated by $2^n/n$.
**2. (Easy–Medium) Closure of P.** Prove that if $A\le_p B$ and $B\in\mathrm P$ then $A\in\mathrm P$. Where exactly is closure of polynomials under composition used?
Solution Let $f$ be the reduction, computable in time $O(n^a)$, and let $M_B$ decide $B$ in time $O(m^b)$. On input $x$ of size $n$: compute $y=f(x)$ in $O(n^a)$; crucially $|y|\le O(n^a)$ (a TM writes at most one symbol per step). Then run $M_B(y)$ in $O(|y|^b)=O(n^{ab})$. Total $O(n^a + n^{ab})=O(n^{ab})$, polynomial. Composition is used twice: $|y|$ is polynomial in $n$, and a polynomial *of* a polynomial ($n^{ab}$) is again polynomial. $\blacksquare$
**3. (Medium) Verifier for CLIQUE.** Give a formal $\mathrm{NP}$ verifier for $\mathrm{CLIQUE}=\{\langle G,k\rangle : G\text{ has a }k\text{-clique}\}$: state the certificate, the check, and its running time, confirming $\mathrm{CLIQUE}\in\mathrm{NP}$.
Solution Certificate $u$ = a list of $k$ vertices, length $O(k\log|V|) = \mathrm{poly}(n)$. Verifier $V(\langle G,k\rangle, u)$: (i) check $u$ lists $k$ *distinct* vertices of $G$; (ii) check all $\binom{k}{2}$ pairs are edges of $G$. Step (ii) is $O(k^2)$ adjacency lookups, polynomial in the input. $V$ accepts iff a valid clique is presented, so $\langle G,k\rangle\in\mathrm{CLIQUE}\iff\exists u: V=1$. Hence $\mathrm{CLIQUE}\in\mathrm{NP}$.
**4. (Medium) coNP certificates.** Explain why TAUTOLOGY (every assignment satisfies $\varphi$) is in $\mathrm{coNP}$ but not *obviously* in $\mathrm{NP}$. What would a short *yes*-certificate need to do, and why is that suspicious?
Solution $\overline{\mathrm{TAUT}} = \{\varphi : \varphi \text{ is falsifiable}\}$ is in $\mathrm{NP}$: certificate = a *falsifying* assignment, checked in polynomial time. Hence $\mathrm{TAUT}\in \mathrm{coNP}$. For $\mathrm{TAUT}\in\mathrm{NP}$ we would need a *short, poly-checkable* proof that $\varphi$ is true under **all** $2^v$ assignments. No such proof system is known; if one existed for all tautologies it would imply $\mathrm{NP}=\mathrm{coNP}$, which is believed false. (Indeed $\mathrm{TAUT}$ is $\mathrm{coNP}$-complete.)
**5. (Hard) Self-reducibility.** Show that if SAT (the *decision* problem) is in $\mathrm P$, then one can *find* a satisfying assignment in polynomial time. Conclude that the search and decision versions of SAT are polynomially equivalent.
Solution Suppose a poly-time decider $D$ for SAT. Given satisfiable $\varphi(x_1,\dots,x_v)$: set $x_1:=\text{T}$ and ask $D(\varphi|_{x_1=T})$. If satisfiable, fix $x_1=\text{T}$; else $D(\varphi|_{x_1=F})$ must return satisfiable (since $\varphi$ was), so fix $x_1=\text{F}$. Recurse on the remaining variables. This makes $\le 2v$ calls to $D$, each on a formula no larger than $\varphi$, so total time is $\mathrm{poly}(|\varphi|)$. The constructed assignment satisfies $\varphi$ by induction. Thus decision $\in\mathrm P \Rightarrow$ search $\in\mathrm{FP}$; the reverse is trivial. SAT is **self-reducible**.
**6. (Hard) Where quantum is *not* magic.** Grover searches an unstructured space of size $N=2^n$ in $\Theta(\sqrt N)=\Theta(2^{n/2})$ queries, provably optimal in the black-box model. (a) Why does this *not* put NP-complete problems in $\mathrm{BQP}$? (b) Contrast with factoring.
Solution (a) For an NP-complete problem with $n$-bit certificates, treating verification as a black box and "Grovering" over $2^n$ candidates costs $\Theta(2^{n/2})$ — still **exponential** in $n$, merely a square-root speedup. Polynomial time would require an *exponential* speedup, which the optimal-query lower bound forbids for *unstructured* search. So quantum does not collapse $\mathrm{NP}$ into $\mathrm{BQP}$; $\mathrm{NP}\subseteq\mathrm{BQP}$ is not believed. (b) Factoring is **structured**: Shor exploits the periodicity of $a^x\bmod N$ via the quantum Fourier transform to get a genuine *polynomial*-time algorithm — an exponential speedup that *does* place $\mathrm{FACTOR}\in\mathrm{BQP}$. The lesson: quantum exponential speedups need structure; brute force only gets a quadratic discount.
--- ## Checkpoint
1. Define $f=\Theta(g)$ and give one $f,g$ with $f=O(g)$ but $f\ne\Theta(g)$. $f=\Theta(g)$ means $f=O(g)$ *and* $f=\Omega(g)$ (same growth rate). Example: $f(n)=n$, $g(n)=n^2$ has $f=O(g)$ but $f=o(g)$, so $f\ne\Theta(g)$.
2. Why does classifying languages capture all of computation? Search and optimization problems reduce to polynomially many decision queries via self-reduction / binary search. So the difficulty of *languages* determines the difficulty of everything.
3. Give the verifier-based definition of $\mathrm{NP}$ in one sentence. $L\in\mathrm{NP}$ iff there is a poly-time verifier $V$ and polynomial $p$ such that $x\in L$ exactly when some certificate $u\in\{0,1\}^{p(|x|)}$ makes $V(x,u)=1$.
4. What is the single consequence of one NP-complete problem being in P? $\mathrm P=\mathrm{NP}$: a polynomial algorithm for any NP-complete problem, composed with the reductions, solves *every* $\mathrm{NP}$ problem in polynomial time.
5. State the inclusion chain placing $\mathrm{BQP}$, and which links are open. $\mathrm P\subseteq\mathrm{BPP}\subseteq\mathrm{BQP}\subseteq\mathrm{PSPACE}$. All inclusions are proven; $\mathrm{BQP}\subseteq\mathrm{PSPACE}$ is a theorem, while $\mathrm{BPP}\subsetneq\mathrm{BQP}$ is *conjectured* (Shor) and $\mathrm{NP}$ vs. $\mathrm{BQP}$ is open/incomparable.
6. True or false: quantum computers efficiently solve NP-complete problems. Justify. **False (as far as is known).** Grover gives only a quadratic speedup for unstructured search, $\Theta(2^{n/2})$ — still exponential — and that is optimal. Quantum's exponential wins (Shor) are on *structured* problems like factoring, which is not known to be NP-complete.
--- ## Further Reading - **[Sip §7.1–7.4]** Sipser — asymptotics, $\mathrm P$, $\mathrm{NP}$, NP-completeness, Cook–Levin. The most readable first treatment; the SAT and 3-SAT material here follows it. - **[AB §2, §7]** Arora & Barak — rigorous $\mathrm{NP}$, reductions, Cook–Levin, $\mathrm{BPP}$ and error amplification; §0.3 for asymptotic notation. - **[AB §4]** Arora & Barak — space complexity and $\mathrm{PSPACE}$ (TQBF completeness). - **[NC §3.2]** Nielsen & Chuang — computational complexity classes oriented toward quantum, including $\mathrm{BPP}$ and the lead-in to $\mathrm{BQP}$. - **[Aar]** Aaronson — sharp intuition for $\mathrm P/\mathrm{NP}/\mathrm{BQP}$ and the (mis)belief that quantum solves NP-complete problems. --- ← Prev: [Models of Computation](01-models-of-computation.md) · Up: [Term 0](../README.md) · Next: [Reversible Computation](03-reversible-computation.md) →