Theory of Computation
Yao Class
Spring 2012 (Turing
Centenary!)
Instructor:
Iddo Tzameret
tzameret@tsinghua.edu.cn
FIT 4-606-3
Office Hours: Fri 3-5pm
Teaching Assistant:
Xiaohong Hao
haoxiaohong.ivy@gmail.comTA's will have office hours from 7:30-8:30pm the night before HW is due.
Course Information:
Time: Wed 1:30-16:05pm
Place: 6B212TA session: TBA
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 presents the basics of
computation theory. The goal is to supply the students with the most
fundamental concepts underlying computation, as developed from the beginning of
the 20th century and onward.
We
shall advance from simple computational models such as Finite Automata and
Regular languages to Context-Free Grammars, and then go to Turing machines, that is--according to the Church-Turing
Thesis--the ultimate model of computation, which can compute any function that
can potentially be computed by any potential computer.
We
then learn undecidability of languages, i.e., functions (or languages) that
cannot be computed by Turing machines. We shall learn basic concepts from
mathematical logic to enable the student familiarity with this essential topic
in computer science.
The
last part is dedicated to Computational Complexity Theory, whose aim is to
understand and classify computational problems according to the resources they
require (for example, computational problems that require short time to solve
versus those that require a lot of time). We will learn the complexity classes
P, NP-complete, PSPACE, BPP, and more.
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
|
2/22
|
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
|
|
2/29
|
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/7
|
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/14
|
Turing
machines formally, levels of descriptions and examples. Equivalence
to other variants, decidability, recognizability, and enumeration.
|
Sipser Chapter 5
|
|
3/21
|
Describing
TMs, Church-Turing Thesis, Hilbert's 10th problem, decidable &
undecidable languages, counting and diagonaliztaion, Acceptance problem is
undecidable.
|
Sipser Chapter 5
|
|
|
3/28
|
Reductions,
Halting problem, Rice Theorem, reductions via configuration transcript,
many-one reductions
|
Sipser Chapter 5,6
|
|
|
4/4
|
Holiday
|
|
|
|
Part
3: Logic and provability
|
4/11
|
Propositional logic, semantics, propositional sequent
calculus, soundness and completeness, compactness.
|
Cook, Nguyen, ASL, Cambridge press, 2010: Chapter 1
|
|
4/17
|
First-order logic, models, first-order sequent calculus,
soundness and completeness.
|
Cook, Nguyen, Chapter 1
|
|
|
Part
4: Computational Complexity
|
Lec 9
|
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
|
|
|
|
|
|
|
|
Lec 10
|
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
|
|
|
Lec 11
|
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
|
|
|
Lec 12 (Periklis Papakonstan-tinou)
|
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
|
|
|
Lec 13
|
Shannon circuit
lower bound (counting), TIME(f(n)) implies
circuit-size O(f2(n)), Probabilistic algorithms, BPP, success
probability amplification
|
Sipser Chapter
9,10
|
|
|
Lec 14
|
Interactive
proofs, definition of model, IP=PSAPCE (only #SAT in IP and IP in PSPACE).
|
Sipser Chapter
10
|
|
Textbooks
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: