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), 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.

---

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<d\le B$. Checking $d\mid N$ is one long division, $O(n^2)$ time — polynomial in $n$. So $\mathrm{FACTOR}\in\mathrm{NP}\cap\mathrm{coNP}$.
• Naïve solving is exponential: trial-dividing by $2,3,\dots,\lfloor\sqrt N\rfloor$ takes $\Theta(\sqrt N) = \Theta(2^{n/2})$ divisions. Doubling the bit length $n$ squares the work.

This $O(n^2)$-to-verify but $2^{\Theta(n)}$-to-solve gap is the texture of $\mathrm{NP}$. Factoring is not believed NP-complete (it is in $\mathrm{NP}\cap\mathrm{coNP}$, and NP-complete problems there would imply $\mathrm{NP}=\mathrm{coNP}$), and — crucially — Shor's quantum algorithm factors in polynomial time, $O(n^3)$-ish, placing $\mathrm{FACTOR}\in\mathrm{BQP}$. That is the quantum speedup, on a structured problem, and it is the concrete evidence for $\mathrm{BPP}\subsetneq\mathrm{BQP}$.

---

Hands-on (Python)

Self-contained, dependency-free. A brute-force 3-SAT solver lets us feel the exponential blow-up: its work scales as $2^v$ in the number of variables $v$, while a verifier given an assignment is instant. We also implement the 3-SAT $\to$ INDEPENDENT-SET reduction from Example 1 and check the two answers agree.

"""Complexity Classes — brute-force SAT + a reduction demo (plain Python)."""

from itertools import product
import time

# A CNF formula is a list of clauses; a clause is a list of literals.
# A literal is a signed int: +i means variable x_i, -i means NOT x_i.  (i >= 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 · Up: Term 0 · Next: Reversible Computation →