CSE 531: Complexity Theory
Final exam preparation
The final exam will cover essentially the entire course including the following
topics.
Time Complexity
- Definitions of TIME(t(n)) and NTIME(t(n))
- Definitions of P and NP.
- Polynomial time algorithms for specific problems.
- NP and NP-completeness
- Equivalent NP characterizations in terms of polynomial-time verifiers
and NTIME, NP algorithms for specific problems.
- Polynomial-time mapping reductions, NP-hardness, NP-completeness
- Cook-Levin Theorem: Tableau idea to prove CIRCUIT-SAT is NP-complete; reduction from
CIRCUIT-SAT to 3SAT.
- The fact that the following problems are NP-complete: CLIQUE, VERTEX-COVER, U/HAMILTONIAN-PATH/, SUBSET-SUM.
- Ability to show other problems NP-complete using these.
Space Complexity
- Definition of SPACE(s(n)) and NSPACE(s(n))
- Relationships of TIME and SPACE
- NTIME(t(n)) in SPACE(t(n)).
- NSPACE(s(n)) in TIME(n2O(s(n))).
- Savitch's Theorem. NSPACE(s(n)) in SPACE(s(n)2).
- PSPACE, PSPACE-completeness.
- PSPACE-completeness of TQBF
- Sub-linear space classes and reductions
- L, NL
- Log-space reductions, NL-completeness
- NL-completeness of PATH.
- NL=coNL.
- P-completeness under logspace reductions
- P-completeness of CIRCUIT-VALUE.
Diagonalization to get complexity lower bounds
- A little more time/space usually helps: TIME and SPACE hierarchy theorems.
- Relativization and oracle TMs
- The fact that P vs NP does not `relativize' so diagonalization will
probably fail to show $P\ne NP$.
Alternating Turing Machines
- Alternation, time, and space: AL=P, AP = PSPACE, APSPACE = EXP.
- Bounded number of alternations and Polynomial-time hierarchy; characterization in terms of oracle machines.
Randomized computation
- Definitions of BPP, RP.
- Amplification of success probability.
- BPP has polynomial sized circuits.
- BPP is in the second level of the hierarchy.
- Search problems solvable in randomized polynomial time but not known be in P
- Finding an n-digit prime
- Finding a quadratic non-residue and finding square roots modulo a prime.
- Randomized polynomial identity testing and applications
- Equivalence testing of Read-Once Branching Programs.
Non-uniform models of computation
- Circuit families
- Branching programs.
Interactive Proofs
- Proving statements beyond NP via interaction with randomized verifier
- A protocol for graph non-isomorphism
- Artithmetization of SAT and interactive protocol for #SAT
- Interactive protocol for TQBF and IP=PSPACE
Derandomization
- Pseudorandom distributions and generators
- Hardness vs. randomness: Pseudorandom generators from average-case hard functions
- P=BPP if TIME(2O(n)) has functions of exponential circuit complexity.