Theory of Computation

Yao Class

Spring 2012 (Turing Centenary!)


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

Teaching Assistant:

Xiaohong Hao

TA'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: 6B212

TA 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



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



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




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!!