Advanced Topics in Classical Complexity Theory
Stub. Coping with intractability (approximation algorithms) and with apparent hardness (probabilistic algorithms, the class BPP, primality testing, read-once branching programs); alternation and the polynomial-time hierarchy; interactive proof systems and the IP = PSPACE theorem; parallel computation (NC and P-completeness); and the basic complexity-theoretic vocabulary of cryptography (one-way and trapdoor functions).
Corresponds to Sipser, Chapter 10, the last chapter of the undergraduate treatment and the direct on-ramp to the advanced course’s material. Approximation and probabilistic algorithms are the two standard responses to NP-hardness in practice: accept a provably near-optimal answer, or accept a small, provable error probability (the class BPP, illustrated by randomized primality testing). Alternation generalizes nondeterminism (which only “exists”-quantifies) to alternating exists/forall quantifiers, characterizing the polynomial-time hierarchy — a presumed-infinite tower of classes between NP and PSPACE. Interactive proof systems generalize NP proofs further still, letting a randomized, polynomial-time verifier have a multi-round conversation with an all-powerful (but untrustworthy) prover; the striking IP = PSPACE theorem says this buys enormous extra proving power — see interactive-proofs-and-the-pcp-theorem for the advanced course’s treatment of interactive proofs and their descendant, the PCP theorem. Parallel computation (the class NC, problems parallelizable to polylogarithmic time) and basic cryptographic vocabulary (one-way and trapdoor functions, the complexity-theoretic basis of public-key crypto — see public-key-cryptography-foundations for the full cryptographic treatment) round out the chapter.
Outline (TODO — flesh out each)
- Approximation algorithms
- Probabilistic algorithms — the class BPP, primality, read-once branching programs
- Alternation — alternating time and space, the polynomial hierarchy
- Interactive proof systems — graph nonisomorphism, IP = PSPACE
- Parallel computation — uniform Boolean circuits, NC, P-completeness
- Cryptography — secret keys, public-key cryptosystems, one-way/trapdoor functions