CSE 200, Computability and Complexity, Fall, 2016

Prof. Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114

Office: 4248 Computer Science Building, EBU3b
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu


Class Times: Tu. Th. 11-12:20, Pepper Canyon 120
TA: Jiawei Gao
Russell's Office Hours: Monday, Wed., Friday, 4-5 4248 CSE, or 4258 if it is crowded
Jiawei's Office Hours: Tu, Th: 2:00-3:00, 4217 CSE (Waiting for departmental approval on the room reservation so may change)

Announcements:
Office hours today are postponed until after the party. I'll stay until no one is waiting. The class description mentioned a project. This is an idea I had but abandonned as impractical, and forgot to remove, replacing it with an additional homework assignment. The class description has been updated. DO NOT PANIC! THERE IS NO PROJECT DUE! Course Handouts

  1. READ THIS!!!!!!! Class Description (pdf)
  2. Homework 1 due Sept. 29. See class description for guidelines
  3. Homework 1 answers. See class description for guidelines
  4. Homework 2 due Oct. 20
  5. Homework 2 answer key
  6. Homework 3 due Nov. 3
  7. Homework 3 answer key
  8. Homework 4 due Nov. 22
  9. Homework 4 answer key
  10. Homework 5 due Dec. 1
  11. Take-home final
The older lecture notes are by Chris Calabro from Fall, 2008, updated by William Matthews. More recent lecture notes from Winter, 2016 are by Jiawei Gao.
  1. [Updated 02/09/16] 1 tape vs multi-tape TMs.
  2. RAMs and circuits
  3. Simulating TMs by circuits
  4. Diagonalization
  5. Reductions
  6. Undecideability of tiling problems
  7. Undecideability of tiling problems
  8. NP and NP-completeness, part 1
  9. [Updated this year] The class NP
  10. [Updated this year] NP-completeness
  11. Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT (A bit redundant)
  12. NP-completeness of combinatorial problems
  13. [Updated this year] NP-complete problems (I)
  14. [Updated this year] NP-complete problems (II)
  15. [New this year]Coping with NP-completeness, Polynomial hierarchy
  16. Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
  17. [Updated this year]Polynomial hierarchy
  18. Space complexity, part 1 (pdf)
  19. Space complexity, part 2 (pdf)
  20. [Updated this year]Space complexity
  21. [Updated this year]Space complexity: NL=co-NL
  22. Randomized algorithms and Probabilistic proofs (pdf)
  23. [Updated this year]Probabilistic Algorithms: polynomial identity testing
  24. [Updated this year]Probabilistic Algorithms: BPP
    Slides from class
  1. The Church Turing thesis
  2. One tape vs Multitape Turing machines
  3. Tiling problem is undecidable (incomplete) s
  4. Boolean circuits
  5. NP
  6. NP-completeness
  7. Diversity of NP-completeness
  8. PH