Theory of Computation
CS Pilot (Yao) Class, Tsinghua Univ.
Spring 2013
Instructor:
Iddo Tzameret
tzameret@tsinghua.edu.cn
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 112TA 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
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.
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,
non-regular languages: the pumping lemma,
|
Sipser, Section 2, note on Myhill-Nerode
Theorem [Trevisan and Williams, Stanford
course].
|
|
|
3/11
|
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
|
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, Church-Turing 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,
many-one 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
|
First-order
logic, models, first-order 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 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
|
|
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 s-t-connectivity, NL vs.
L.
|
Sipser Chapter 8
|
|
|
5/13
|
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
|
|
|
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:
Baker-Gil-Solovay Theorem, Boolean circuit
complexity.
|
Sipser Chapter 9
|
|
|
5/27
|
Shannon circuit lower bound (counting), TIME(f(n))
implies circuit-size O(f2(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: