Theory of Computation
CS Pilot (Yao) Class, Tsinghua Univ.
Spring 2013
Instructor:
Iddo Tzameret
tzameret@tsinghua.edu.cn
FIT 46063
Office Hours: Fri 35pm
Teaching Assistant:
Yuzhao Wu
TA's will have office hours from 7:308:30pm the night before HW is due.
Course Information:
Time: Mon 13:3016:05
Place: XueTang 112TA session (not every week):
Time: Mon 16:1016: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
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, contextfree grammars,
Turing machines, diagonalization, undecidability, basic propositional and
firstorder logic and basic computational complexity theory including P, NP,
NPcompleteness, 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.
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

2/25

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


3/4

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

Sipser, Section 2, note on MyhillNerode
Theorem [Trevisan and Williams, Stanford
course].



3/11

MyhillNerode
theorem, minimization of DFA's, ContextFree 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

3/18

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

Sipser Chapter 5


3/25

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

Sipser Chapter 5



4/1

Reductions,
Halting problem, Rice Theorem, reductions via configuration transcript,
manyone reductions

Sipser Chapter 5,6



Part 3: Logic and provability

4/8

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

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


4/15

Midterm
exam



4/22

Firstorder
logic, models, firstorder sequent calculus, soundness and completeness.

Cook, Nguyen, Chapter 1



Part
4: Computational Complexity

4/29

Intro to complexity, Time complexity, Time bounds for TMs,
Relations between 1 and ktape 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: CookLevin theorem,
Recap of known polynomial reductions, coNP

Sipser Chapter 7


5/6

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

Sipser Chapter 8



5/13

Logspace
reductions, NL completeness, directed st connectivity is NL complete, NL=coNL (ImmermanSzlepeceney
’87), Hierarchy theorems: Space hierarchy, NL proper subclass of
PSPACE. PSPACE proper subclass of EXPSPACE.

Sipser Chapter 8, 9



5/20

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:
BakerGilSolovay Theorem, Boolean circuit
complexity.

Sipser Chapter 9



5/27

Shannon circuit lower bound (counting), TIME(f(n))
implies circuitsize O(f^{2}(n)), Probabilistic algorithms, BPP,
success probability amplification

Sipser Chapter 9,10



6/3

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: