CSE 200, Computability and Complexity, Winter 2018

This class is an introduction to computational complexity theory. This area aims to understand the various resources needed to solve computational problems. Such resources include the obvious ones, such as time and memory, but also possibly less obvious ones, such as randomization, interaction and non-uniformity. In addition, we will attempt to classify problems as "easy" or "hard", study relations between easy and hard problems, as understand why the "P vs NP" problem is possibly the most important open problem in computer science, mathematics and science at large.


Class Times: M,W 10:30-11:50, EBU3B (CSE building), room 4140
Instructor: Shachar Lovett, slovett@ucsd.edu, Office hours: TBD
TA: Marco Carmosino, mcarmosi@ucsd.edu, Office hours: TBD


Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, 1st edition, 2009. Online version (draft)


  1. Models of computation: Turing Machines and variants, RAM model, Boolean circuits. Simulating one machine model with another. The Church-Turing thesis and versions for efficient computation (Chapters 1, 3, and 6)
  2. Universal machines and diagonalization: Undecidability. Recursive enumerability. The Halting Problem. Time and Space Hierarchy Theorems. Reductions. (Chapter 3).
  3. NP-completeness and the P vs NP question. Consequences of P = NP. The polynomial-time hierarchy. (Chapters 2 and 5)
  4. Space Complexity (Chapter 4)
  5. Randomized computing (Chapter 7)
  6. Time permitting: Interactive proofs (Chapter 8), Quantum computation (Chapter 10)


4 homework sets and a final project, each worth 20%.


To appear


To appear

Tentative schedule: