Computation and Turing Machines: Turing machines, 3-tape TM for Palindromes, lower-bound for 1-tape TM for palindromes. |

Universal Turing Machines and Undecidability: Dependence on number of tapes & alphabet size, Universal TMs, uncomputable functions, HALT undecidable. |

The Class P: Definition of P, Boolean formulea, satisfiability, 2-CNF in P, reduction of 2-coloring to 2-CNF. |

The Class NP: Certificate definition of NP, Non-deterministic TMs and equivalence to NP, polynomial-time reducibility. |

The Cook-Levin Theorem: Relation between Boolean functions and satisfiability, Cook-Levin theorem, CNF reducible to 3-CNF. |

NP hardness Reductions: NP-hardness reductions for Independent set, Vertex-cover, Integer Programming. |

Further NP hardness Reductions: NP-hardness reductions for Hamiltonian cycle and Knapsack problem. |

Search vs Decision and coNP: Decision vs. optimization, coNP, relation between NP and coNP. |

Space Complexity 1: Definition of space complexity, PSPACE, relation to NP & DTIME, Quantified Boolean Formulas (QBF), QBF is in PSPACE. |

Space Complexity 2: Proof of SPACE(o(loglogn)) = SPACE(O(1)), Nondeterministic space complexity. |

Nondeterministic Space Complexity: Reachability in NSPACE(log n) & SPACE(log^2 n), Savitch's theorem, Class L & its certificate definition, log-space reductions. |

Complement Space Complexity: coPSPACE & coNL, Proof of Immerman-Szelepscenyi theorem. |

The Polynomial Hierarchy: Properties of class &sum 2, polynomial hierarchy, P=NP implies collapse of PH, complete problems for PH, defining PH via oracle TMs, TISP. |

Randomized Computation 1: Polynomial identity testing, probabilistic TMs, classes RP, coRP, BPP & ZPP, boosting probabilities. |

Randomized Computation 2: Proof of ZPP = RP &cap coRP, proof of BPP = &sum 2 |

Interactive Proofs: Deterministic proof systems, equivalence to NP, interactive proof systems, authentication without giving password, IP for graph non-isomorphism. |

Interactive Proofs: co3SAT: Proof of co3SAT is in IP. |

Interactive Proofs: IP = PSPACE : Proof of #SAT is in IP, sketch of proof of IP=PSPACE theorem. |

Probabilistically Checkable Proofs: 7/8-approximation for 3-SAT, probabilitically checkable proofs, PCP(logn, poly(n)) ⊆ NP, gap-producing functions & PCP theorem. |