cse 431: intro to theory of computation, winter 2018

CSE 431: Theory of Computation

Winter, 2018

T Th 12-120pm EEB 037

Instructor: James R. Lee (jrl@cs)

Office hours: F 2:30-3:30pm, CSE 640 (or by appointment)

TA : Yuqing Ai (yuqingai@cs)

Office hours: N/A

TA: Alireza Rezaei (arezaei@cs)

Office hours: F 1:30-2:30pm, CSE 220

Email and discussion:

Class email list: cse431a_wi18 [click link to sign up] [archives]
Discussion forum

Textbook:

Main text: Introduction to the Theory of Computation (3rd ed)
Michael Sipser, PWS Publishing.

Lectures

date	topic	media	reading
4-Jan	Introduction Encoding computational problems as languages (Sec 0.2 in Sipser) Turing machines	pdf slides [epic Game of Life video]	Sipser 3.1-3.3
9-Jan	Turing-recognizable and Turing-decidable languages Universality and simulation The Church-Turing thesis Multi-tape TMs, non-deterministic TMs Homework #1		Sipser 3.1-3.3
11-Jan	Enumerators Algorithms on TMs Turing-decidability Undecidability		Sipser 3.3; 4.1-4.2
16-Jan	Existence of undecidable languages Diagonalization The halting problem Reductions Homework #1 Due Homework #2		Sipser 4.1-4.2; 5.1
18-Jan	Reductions (cont.) Computable functions		Sipser 5.1, 5.3, 6.2
23-Jan	Decidability of logical theories Undecidability in arithmetic Homework #2 Due Homework #3	Logicomix (An epic search for truth)	Sipser 5.3, 6.2
25-Jan	Time complexity P and NP		Sipser 7.1-7.3
30-Jan	NP-completeness Poly-time reductions Homework #3 Due Homework #4		Sipser 7.4-7.5
1-Feb	Cook-Levin Theorem (3SAT is NP-complete) Hamiltonian path is NP-complete 3-Coloring is NP-complete		Sipser 7.4-7.5
6-Feb	SUBSET-SUM The time-hierarchy theorem Diagonalization Oracles and relativizing arguments Homework #4 Due Homework #5		Sipser 9.1-9.2
8-Feb	Space complexity		Sipser 8.1-8.2
13-Feb	MIDTERM Homework #6
15-Feb	Savitch's theorem Homework #6 Due		Sipser 8.1-8.2
20-Feb	NL-completeness		Sipser 8.1-8.2
22-Feb	NL=coNL		Sipser 8.3-8.6
27-Feb	PSPACE and PSPACE-completeness TBQF is PSPACE-complete An interactive proof for graph non-isomorphism Homework #7		Sipser 8.3-8.6
1-Mar	IP and interactive proofs IP is inside PSPACE #SAT is in IP	Polynomial long division	Sipser 10.4
6-Mar	IP=PSPACE		Sipser 10.4
8-Mar	The PCP Theorem	A history of the PCP theorem
15-Mar	FINAL EXAM 10:30am-12:20pm, EEB 037

Topics:

Turing machines and the Church-Turing Thesis
Decidability and the Halting Problem
Reductions
Time complexity
P vs. NP
NP-completeness and the Cook-Levin Theorem
Space complexity
Interactive proofs and IP=PSPACE
Advanced topics

Grading:

50% Homework, 15% Midterm, 35% Final

Homeworks

Due on Tuesdays before 11:59am.

Related material:

Scott Aaronson's Who can name the bigger number?
Alan Turing's 1936 paper On computable numbers, with an application to the Entscheidungsproblem.
A New Yorker article about Alan Turing.
Hilbert's 23 problems (Problems 2 and 10 are of relevance to this course.)
An interesting popular review of a book about Kurt Godel.
A New Yorker article: "What were Einstein and Godel talking about?"
The Algorithm: Idiom of Modern Science
Logicomix: An epic search for truth