CSE 531 Introduction to Formal Models in Computer Science

Final exam preparation

The final exam is Monday, December 12 at 10:30-12:20 in our regular classroom. The exam will be closed book but you may bring this list to the exam.

The final exam will cover essentially the entire course including the following topics.

• Turing machines and undecidability

  1. Basic definitions of Turing machines and their operations.

  2. Turing recognizable, decidable languages.

  3. Turing machines as language enumerators.

  4. Church-Turing thesis and evidence for it: simulations of multitape and nondeterministic TMs.

  5. Decision procedures for properties of automata, CFLs, PDAs, etc.

  6. Undecidability and reductions

     • Diagonalization and countability.

     • Undecidability of the Halting problem.

     • Turing-recognizable and coTuring-recognixable implies decidable.

     • (Mapping) reductions to show other problems undecidable, not Turing-recognizable.

     • Undecidability by computation histories, undecidable properties of CFLs, Post Correspondence Problem.

     • Turing reductions.

• Complexity

  1. Definitions of TIME(t(n)) and NTIME(t(n))

  2. Definitions of P and NP.

  3. Polynomial time algorithms for specific problems.

  4. 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, INDEPENDENT-SET, VERTEX-COVER, U/HAMILTONIAN-PATH/CIRCUIT, 3COLOR, SUBSET-SUM.

     • Ability to show other problems NP-complete using these.

  5. Definition of SPACE(s(n)) and NSPACE(s(n))

  6. Relationships of TIME and SPACE

     • NTIME(t(n)) in SPACE(t(n)).

     • NSPACE(s(n)) in TIME(n2^O(s(n))).

  7. Savitch's Theorem. NSPACE(s(n)) in SPACE(s(n)²).

  8. PSPACE, PSPACE-completeness.

  9. PSPACE-completeness of TQBF

  10. Polynomial-time oracle TMs.

  11. Polynomial-time hierarchy and characterization in terms of bounded alternation TQBF.

  12. Low-level space

      • L, NL

      • Log-space reductions, NL-completeness

      • NL-completeness of PATH.

      • NL=coNL.

  13. P-completeness.

  14. P-completeness of CIRCUIT-VALUE.

  15. Diagonalization to get complexity lower bounds

      • A little more time/space usually helps: TIME and SPACE hierarchy theorems.

      • The fact that P vs NP does not `relativize' so diagonalization will probably fail to show $P\ne NP$.

  16. Randomized computation

      • Definitions of BPP, RP.

      • Amplification of success probability.

      • The fact that PRIMES in BPP (COMPOSITES in RP).

      • Randomized polynomial identity testing.

  17. Non-uniform models of computation

      • Circuit families

      • Branching programs.