Section outline

  •  Week 2

    • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. 
    • Basic notions and results of Complexity Theory: Separating complexity classes via diagonalization, proving inclusion of complexity classes via simulation.  Overview of deterministic and nondeterministic time and space classes. Certificate characterizations.