Multitape Turing machines; Simulation of multitape Turing machines by single-tape Turing machines; Diagonalization; Undecidability of the halting problem.

Sec 3.2 and 4.2 of TC Sec 2.2, 2.3, 3.1 and 3.2 of CC

More topics (We will have the final in the registrar assigned slot of 12/22/2016 between 7:10 and 10pm.)

HW 4 due on Dec 13

CC: Computational Complexity TC: Introduction to the Theory of Computation MA: Computational Complexity: A Morden Approach LC: Lectures in Computational Complexity (by Jin-Yi Cai)

## Date

## Topic

## Readings

## Notes

## Homework

Chapter 1 and Sec 2.1 of CC

Turing machines by single-tape Turing machines;

Diagonalization; Undecidability of the halting problem.

Sec 2.2, 2.3, 3.1 and 3.2 of CC

PSPACE; Linear speedup; PSPACE is in EXPTIME;

and the Space hierarchy theorem.

Sec 2.4, 2.5, 7.1 and 7.2 of CC

Nondeterministic Turing machines.

Sec 3.1, 7.2 and 2.7 of CC

recursion; Generalized Geography is in PSPACE.

Sec 7.1 of CC

NL = coNL.

Sec 7.3 of CC

from 3SAT to Clique; NP-completeness of SAT.

Sec 8.1, 8.2 and Chapter 9 of CC

path, and Subset-sum.

Chapter 9 of CC

PSPACE-completeness of TQBF.

Sec 19.1 of CC

the Polynomial Hierarchy; consequence of P = NP.

Sec 17.2 of CC

Sec 14.3 of CC

Sec 4.1 of LC

a randomized algorithm for MAXCUT.

Sec 5.2.2 of LC

inequalities; Chernoﬀ bound; Randomized

complexity classes; Amplification of RP and BPP.

and Sec 5.4 of LC

and Sec 5.6 of LC

Razborov-Smolensky Theorem

Switching Lemma

assigned slot of 12/22/2016 between 7:10 and 10pm.)

CC: Computational Complexity

TC: Introduction to the Theory of Computation

MA: Computational Complexity: A Morden Approach

LC: Lectures in Computational Complexity (by Jin-Yi Cai)