Computability and Complexity PPT

Instructor:Sanjit A. Seshia

Course Description

This course will introduce you to three foundational areas of computer science:

• Automata Theory: What are the basic mathematical models of computation?
• Computability Theory: What problems can be solved by computers?
• Complexity Theory: What makes some problems computationally hard and others easy?

Specific topics include: Finite automata, Pushdown automata, Turing machines and RAMs. Undecidable, exponential, and polynomial-time problems. Polynomial-time equivalence of all reasonable models of computation. Nondeterministic Turing machines. Theory of NP-completeness: Cook's theorem, NP-completeness of basic problems. Selected topics in language theory, complexity and randomness.  

Textbooks

The required textbook for this course is the following:

Author: Michael Sipser

Title: Introduction to the Theory of Computation

Publisher: Course Technology (Thomson)

Year/Edition: 2nd edition, 2005

Acronym: Sipser

The following books are recommended for further reading:

1. Authors: John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman
   Title: Introduction to Automata Theory, Languages, and Computation
   Publisher: Addison-Wesley
   Year/Edition: 2nd or 3rd edition
   Acronym: HMU
   
2. Author: Christos Papadimitriou
   Title: Computational Complexity
   Publisher: Addison-Wesley
   Year/Edition: 1994
   Acronym: CP
   
3. Authors: Michael Garey and David Johnson
   Title: Computers and Intractability
   Publisher: Freeman
   Year/Edition: 1979
   Acronym: GJ 

Course Slides

Lec.	Topics (with PDFs of lecture slides, if applicable)	Required Reading
1	Course Overview; Introduction to Finite Automata (PDF2up, PDF )	Sipser Ch. 0, 1.1
2	Finite Automata: DFAs and NFAs ( PDF2up, PDF )	Sipser 1.1, 1.2
3	Equivalence of DFAs and NFAs, closure of regular operations ( PDF2up, PDF )	Sipser 1.2
4	Regular expressions and equivalence with finite automata ( PDF2up, PDF )	Sipser 1.3
5	Pumping lemma and non-regular languages (no slides)	Sipser 1.4
6	Minimization of DFAs; the Myhill-Nerode theorem ( PDF2up, PDF )	Handout
7	Context-free languages: introduction (no slides)	Sipser 2.1
	President's day, no lecture
8	Pushdown automata; equivalence with CFL ( PDF2up, PDF )	Sipser 2.2
9	PDA-CFL equivalence; Pumping lemma for CFLs ( PDF2up, PDF )	Sipser 2.3
10	Examples of non-CFLs; Context-sensitive languages; the Chomsky hierarchy (no slides)	Sipser 2.3
11	No lecture -- midterm
12	Turing machines; the Church-Turing thesis ( PDF2up, PDF )	Sipser 3.1, 3.3
13	TM examples and TM variants	Sipser 3.2
14	Decidable languages	Sipser 4.1
15	Diagonalization; The Halting Problem	Sipser 4.2
16	Reductions between problems; mapping reducibility	Sipser 5.1, 5.3
	Spring break
	Spring break
18	Time complexity; The class P	Sipser 7.1, 7.2
19	The classes NP and co-NP; Examples; Polynomial-time reductions	Sipser 7.3, 7.4
20	NP-completeness; examples	Sipser 7.4, 7.5
21	Proof of Cook-Levin theorem, review of reductions	Sipser 7.4
22	PSPACE and NPSPACE; Savitch's theorem	Sipser 8.1, 8.2
23	No lecture -- midterm
24	PSPACE-completeness; The QBF problem	Sipser 8.3
25	The classes L and NL; Log-space reductions; NL-completeness	Sipser 8.4, 8.5
26	The Space Hierarchy Theorem; NP and co-NP; The Time Hierarchy Theorem (start)	Sipser 9.1
27	The Time Hierarchy Theorem (finish); Special topic: Phase transitions in SAT; Wrap-up (PDF)	Sipser 9.1
	RRR week
	RRR week
	Final Exam, 8 - 11 am, in 251 HEARST GYM