## 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.