CSE 200, Computability and Complexity, Winter, 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. 3:30-4:50, WLH 2111
TA: Jiawei Gao
Russell's Office Hours: Monday,12:10-1:50; Wed., Friday, 1-2:20. 4248 CSE, or 4258 if it is crowded
Jiawei's Office Hours: Tu, Th: 1:20-3:20, B260A CSE

Announcements: Russell's office hours Wed. March 16 (aka, day the exam is due), will be moved to 12:00-1:00.
Course Handouts

  1. Class Description (pdf)
  2. Homework 1 due January 12. See class description for guidelines
  3. Homework 1 answer key
  4. Homework 2 due January 26.
  5. Homework 2 answer key
  6. Homework 3 due Feb. 16. NOTE CHANGE
  7. Homework 3 answer key
  8. Homework 4 due March 1
  9. Homework 4 answer key
  10. Homework 5 due March 10
  11. Final exam, due March 16
The following lecture notes are by Chris Calabro from Fall, 2008, and more recently by William Matthews. These may differ from class this year. Jiawei is inserting notes from this year.
  1. 1-tape vs mmulti-tape TMs
  2. [Updated 02/09/16][Updated this year] 1 tape vs multi-tape TMs.
  3. RAMs and circuits
  4. Simulating TMs by circuits
  5. Diagonalization, non-computable sets, and the time hierarchy theorem
  6. [Updated this year] Diagonalization
  7. [New this year] Reductions
  8. Undecideability of tiling problems
  9. [Updated this year] Undecideability of tiling problems
  10. NP and NP-completeness, part 1
  11. [Updated this year] The class NP
  12. [Updated this year] NP-completeness
  13. Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT (A bit redundant)
  14. NP-completeness of combinatorial problems
  15. [Updated this year] NP-complete problems (I)
  16. [Updated this year] NP-complete problems (II)
  17. [New this year]Coping with NP-completeness, Polynomial hierarchy
  18. Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
  19. [Updated this year]Polynomial hierarchy
  20. Space complexity, part 1 (pdf)
  21. Space complexity, part 2 (pdf)
  22. [Updated this year]Space complexity
  23. [Updated this year]Space complexity: NL=co-NL
  24. Randomized algorithms and Probabilistic proofs (pdf)
  25. [Updated this year]Probabilistic Algorithms: polynomial identity testing
  26. [Updated this year]Probabilistic Algorithms: BPP