Theory of Computation

CS Pilot (Yao) Class, Tsinghua Univ.

Spring 2013


Iddo Tzameret
FIT 4-606-3
Office Hours: Fri 3-5pm

Teaching Assistant:

Yuzhao Wu

TA's will have office hours from 7:30-8:30pm the night before HW is due.

Course Information:

Time: Mon 13:30-16:05
Place: XueTang 112

TA session (not every week):

Time: Mon 16:10-16:55

Place: XueTang 112

Course Requirement:

1.      Assignments: ~7 home assignments: 21% of final grade

2.      Midterm exam: 30% of final grade

3.      Final exam: 50% of final grade

Course Description

This course gives an introduction to the basics of computation theory. The goal is to supply the students with the fundamental concepts underlying computation theory, as developed from the beginning of the 20th century, and up to the contemporary era. Specifically, the course presents the basics of finite automata, regular languages, context-free grammars, Turing machines, diagonalization, undecidability, basic propositional and first-order logic and basic computational complexity theory including P, NP, NP-completeness, L, NL, PSPACE, space and time hierarchy theorems, the polynomial hierarchy, relativization, probabilistic complexity classes such as BPP, interactive proofs and statement of the PCP theorem.


Tentative Program

Part 0: Preliminaries

Before class

Mathematical preliminaries (read this if you're not sure you remember basic mathematical notations and concepts).

Sipser Chapter 0


Part 1: Automata and Languages



Administratrivia, overview, languages, deterministic finite automata (DFA): definition, regular languages (definition), regular operations, DFAs are closed under regular operations, nondeterministic finite automata (NFA), DFAs are equivalent to NFAs.

Sipser, Section 1



Regular expressions, regular languages are equivalent to regular expressions, non-regular languages: the pumping lemma,

Sipser, Section 2, note on Myhill-Nerode Theorem [Trevisan and Williams, Stanford course].



Myhill-Nerode theorem, minimization of DFA's, Context-Free Grammars (CFG), context free languages (CFL), ambiguity of CFGs.

Starting computability, Turing machines.

Sipser, Sec. 2, 3, 4.

Alan Turing's original 1936 paper!!


Part 2: Computability



Turing machines formally, levels of descriptions and examples. Equivalence to other variants, decidability, recognizability, and enumeration.

Sipser Chapter 5



Describing TMs, Church-Turing Thesis, Hilbert's 10th problem, decidable & undecidable languages, counting and diagonaliztaion, Acceptance problem is undecidable.

Sipser Chapter 5



Reductions, Halting problem, Rice Theorem, reductions via configuration transcript, many-one reductions

Sipser Chapter 5,6



Part 3: Logic and provability


Propositional logic, semantics, propositional sequent calculus, soundness and completeness, compactness.

Cook, Nguyen, ASL, Cambridge press, 2010: Chapter 1



Midterm exam



First-order logic, models, first-order sequent calculus, soundness and completeness.

Cook, Nguyen, Chapter 1


Part 4: Computational Complexity


Intro to complexity, Time complexity, Time bounds for TMs, Relations between 1 and k-tape TMs: f^2 simulation, The class P=PTIME, Polynomial reductions, The class NP, verifiers, short certificates, NP vs. P problem, importance, NP completeness, SAT is NP complete: Cook-Levin theorem, Recap of known polynomial reductions, coNP

Sipser Chapter 7



Space Complexity, definition of model, Savitch Theorem (‘71), Reachability, PSPACE, PSPACE completeness, Validity of Quantified Boolean Formulas (TQBF) is PSPACE complete, L, NL, directed s-t-connectivity, NL vs. L.

Sipser Chapter 8



Log-space reductions, NL completeness, directed s-t -connectivity is NL complete, NL=coNL (Immerman-Szlepeceney ’87), Hierarchy theorems: Space hierarchy, NL proper subclass of PSPACE. PSPACE proper subclass of EXPSPACE.

Sipser Chapter 8, 9



Time hierarchy: Time(f(n)) proper subclass of Time(g(n)) if f(n)=o(g(n)log (f(n))) [by padding improve to f(n)=o(g(n))]. Cor: P proper subclass of EXPTIME, Relativizations: Baker-Gil-Solovay Theorem, Boolean circuit complexity.

Sipser Chapter 9



Shannon circuit lower bound (counting), TIME(f(n)) implies circuit-size O(f2(n)), Probabilistic algorithms, BPP, success probability amplification

Sipser Chapter 9,10



Interactive proofs, definition of model, IP=PSAPCE

Sipser Chapter 10








1.  The textbook for the class is Michael Sipser's excellent Introduction to the Theory of Computation, second edition.

Additional references:

2.   For Turing Machines and Complexity Theory, you might consult another excellent book: Christos Papadimitriou's Computational Complexity.

3.       For automata theory, regular languages and context free grammars, you might consult the classical: Introduction to Automata Theory, Languages, and Computation (2nd Edition), by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; (the first edition by Aho, Hopcroft and Ullman is recommended).

4.       A potential classic, and more advanced text on computational complexity is: Sanjeev Arora & Boaz Barak's Computational Complexity: A Modern Approach (a draft of which can be found online). Additional references will be posted here.

5.       Stephen Cook, Phuong Nguyen. Logical foundations of proof complexity, ASL, Cambridge press, 2010.

General interest:

1.     Alan Turing's original 1936 paper.