• Overview
• Details
• Exercises

Beyond P and NP lie counting and space/time-bounded classes. #P counts accepting paths of NP machines; PSPACE captures poly-space decision problems; EXPTIME allows exponential time. Classic containments and separations shape complexity theory.

• #P: functions counting witnesses; #SAT is #P-complete (parsimonious reductions). PP, BPP ⊆ P^#P; Toda’s theorem: PH ⊆ P^#P.
• PSPACE: problems solvable with polynomial space; PSPACE-complete via polynomial-time reductions. QBF is PSPACE-complete.
• EXPTIME: time 2^{poly(n)}; EXPTIME-complete problems (generalized chess/checkers on n×n boards). Time hierarchy implies P ⊊ EXPTIME.
• Containments: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Known separations: P ⊊ EXPTIME. Open: P ?= NP, NP ?⊆? PSPACE, PSPACE ?= EXPTIME.
• Savitch’s theorem: NPSPACE = PSPACE; space hierarchy; relationship with EXPSPACE.

1. Show that QBF is PSPACE-complete by reduction from TQBF and outline a poly-space solver.
2. Prove that P ⊊ EXPTIME using the time hierarchy theorem.
3. Define a parsimonious reduction from SAT to #SAT and argue #SAT is #P-complete.