Skip to content

Instantly share code, notes, and snippets.

@ltiao

ltiao/comp4141_study.md

Last active August 29, 2015 14:02
Show Gist options
  • Save ltiao/6985dc4af71aa06766fd to your computer and use it in GitHub Desktop.
Save ltiao/6985dc4af71aa06766fd to your computer and use it in GitHub Desktop.
Download ZIP
Raw
comp4141_study.md

  • Write 2 double sided A4 sheets of handwritten notes (23 June 2014)

    • Polynomial Time Hierarchy
    • Running-time bounds on f(n) space Turing machines
    • Complexity Zoology
    • A language is decideable iff it is Turing-recognizable and co-Turing-recognizable
    • Rice's Theorem
    • List of undecidable problems relating to CFL's etc
    • Different types of reductions (Log-space transducers)
    • Savitches Theorem

  • Week 12 + 13 lectures (20 June 2014)

    • Interactive Proof Systems
    • Recursion Theorem
    • Hierarchy Theorems

  • Read proof on NP-Hardness of SAT and thereby TQBF

  • Partial Message History (computation history)

  • Homework 11

  • Do select Sipser problems for each chapter

  • Review Notes

    • Proof techniques for relating complexity classes
      • NL = coNL
      • Savitches
      • ATIME(f(n)) \subset SPACE(f(n))
    • Showing undecidability, completeness, etc.
    • Turing machine models (enumerators, transducers, multitape, etc)
    • Diagonalization (A_{TM} is undecidable)
    • Savitches Theorem

  • Review Homework

  • SAT is NP-Hard

  • TQBF is PSPACE-Hard

  • Savitches Theorem *

  • NL = coNL *

  • Alternation class equivalences *

  • IP = PSPACE

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment