CSE P531: Computability and Complexity Theory

Spring, 2016

Instructor: James R. Lee (jrl@cs)

Office hours: Wed 530-620pm, CSE 640

TA : Jeffrey Hon (jhon@cs)

Office hours: TBD

Wed 6:30-920pm JHN 175

Email and discussion:

Class email list: csep531a_sp16 [click link to sign up]     [archives]
Discussion board

Textbook:

Lectures

date topic slides reading
30-Mar Cardinality of sets
Turing machines, decidability		 pdf Sipser 3.1-3.3, 4.1-4.2
13-Apr Universal Turing machines
   [epic Game of Life video]
Undecidability of the halting problem
Reductions
Time complexity and polynomial time		 pdf Sipser 5.1-5.3; 7.1-7.2
20-Apr Non-deterministic Turing machines and NP
Polynomial-time reductions and NP-completeness		 Sipser
Arora-Barak		 7.1-7.4
1.5, 2.1-2.3
27-Apr More NP-completeness reductions
  • 3-SAT < HAMPATH
  • HAMPATH < UHAMPATH
  • 3-SAT < SUBSET-SUM
The Cook-Levin Theorem (optional)
 Sipser
Arora-Barak		 7.4-7.5
2.2-2.4
4-May Space complexity
  • PSPACE, NPSPACE
  • Savitch's theorem
Time and space hierarchy theorems
  • Time and space constructibility
  • Bounded resource diagonalization
 Sipser
Arora-Barak		 8.1-8.4, 9.1
4.1-4.3
11-May Interactive proofs and IP=PSPACE
  • Deterministic IP = NP
  • Error amplification by majority vote
  • Graph non-isomorphism
  • IP ⊆ PSPACE
  • Arithmetic encoding of SAT formulas
  • #SAT is in IP
 Arora-Barak 8.1-8.5
18-May Logarithmic space computation
  • Log space TMs; L and NL
  • L ⊆ P
  • Log-space reductions and NL-completeness
  • DIRPATH, NL ⊆ P
  • coNL=NL
 Sipser 8.4-8.6
25-May Randomness and computation
  • TMs with random tape
  • One-sided vs. two-sided error
  • RL
  • Undirected connectivity
  • Random walks and electrical networks
Presentations 		ppt
pdf		 supplementary
1-Jun

Topics:

  • Turing machines, decidability, and reductions
  • Proof systems and Godel's incompleteness theorems
  • P, NP, and NP-completeness
  • Time and Space hierarchy theorems
  • Space complexity and Savitch's theorem
  • Circiut complexity
  • The PCP theorem

Grading:

70% Homework, 30% Project

Homeworks

[ Dropbox for assignments ]

  • HW #1; out 30-Mar, due 8-Apr (9pm)
  • HW #2; out 8-Apr, due 16-Apr (9pm)
  • HW #3; out 14-Apr, due 23-Apr (9pm)
  • HW #4; out 21-Apr, due 30-Apr (9pm)
  • HW #5; out 28-Apr, due 7-May (9pm)
  • HW #6; out 5-May, due 14-May (9pm)
  • HW #7; out 20-May, due 28-May (9pm)
    • Sipser, 8.25 (BIPARTITE in NL)
    • Sipser, 8.27 (STRONGLY-CONNECTED is NL-complete)
    • Extra credit: Sipser, 8.18 (Proper nesting of [()])

Project topics:

(AB refers to the Arora-Barak book)

Related material: