Theory of Computation
Yao Class
Spring 2012 (Turing
Centenary!)
Instructor:
Iddo Tzameret
tzameret@tsinghua.edu.cn
FIT 46063
Office Hours: Fri 35pm
Teaching Assistant:
Xiaohong Hao
haoxiaohong.ivy@gmail.comTA's will have office hours from 7:308:30pm the night before HW is due.
Course Information:
Time: Wed 1:3016: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
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 ContextFree Grammars, and then go to Turing machines, that isaccording to the ChurchTuring
Thesisthe 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, NPcomplete, PSPACE, BPP, and more.
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,
nonregular languages: the pumping lemma,

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



3/7

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/14

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

Sipser Chapter 5


3/21

Describing
TMs, ChurchTuring 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,
manyone 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

Firstorder logic, models, firstorder 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 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







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 stconnectivity,
NL vs. L.

Sipser Chapter
8



Lec 11

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



Lec 12 (Periklis Papakonstantinou)

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



Lec 13

Shannon circuit
lower bound (counting), TIME(f(n)) implies
circuitsize O(f^{2}(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


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: