CSE 200, Computability and Complexity, Spring 2026

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.

Information:

Class Times: MW 10:30-11:50am, CSE 4140
Instructor: Shachar Lovett, email: slovett@ucsd.edu, office hours: Tue 5-6pm, CSE 4234 or zoom
TA: Farzan Byramji, email: fbyramji@ucsd.edu, office hours: Fri 5:30-6:30pm, CSE 4232
Piazza: https://piazza.com/ucsd/spring2026/cse200, used for online forums, Q&A and announcements
Gradescope: https://www.gradescope.com/courses/1272837, used for homework submission. Registration code: WN64JN

Homework:

Homework 1, due April 13, 11:59pm.

Textbook:

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

Lecture notes:

The lecture notes are on Overleaf and will be updated throughout the quarter.

Topics:

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)
Universal machines and diagonalization: Undecidability. Recursive enumerability. The Halting Problem. Time and Space Hierarchy Theorems. Reductions. (Chapter 3).
NP-completeness and the P vs NP question. Consequences of P = NP. The polynomial-time hierarchy. (Chapters 2 and 5)
Space Complexity (Chapter 4)
Randomized computing (Chapter 7)
Time permitting: Interactive proofs (Chapter 8), Quantum computation (Chapter 10)

Evaluation:

Your grade is based on homework, a midterm and a final exam:

(20%) Homework: 4 problem sets, can solve individually or in pairs
(30%) Midterm: In class, May 4, 10:30-11:50am
(50%) Final: In class, June 8, 8-11am

Tentative schedule:

Introduction. Turing machines. Computable functions and robustness under different models.
Universal Turing machines. Uncomputable functions. Definition of time complexity. (Arora-Barak 1.4-1.6).
Time and space complexity and hierarchy theorems. (Arora-Barak 3.1 and 4.1).
NP and NP-completeness. (Arora-Barak 2.1-2.2, 2.5).
NP-completeness: Cook-Levin theorem. (Arora-Barak 2.3).
Beyond NP: the Polynomial Hierarchy. (Arora-Barak 2.6, 5.1-5.2).
Space complexity: Logspace computation. NL completeness. (Arora-Barak 4.1).
Space complexity: PSPACE completeness. Savitch theorem. (Arora-Barak 4.2-4.3).
Space complexity: NL=coNL. Boolean circuits. (Arora-Barak 4.3, 6.1-6.2).
Boolean circuits: Karp-Lipton, Meyer theorems. (Arora-Barak 6.3-6.5).
Boolean circuits lower bounds: PARITY is not in AC0 (see Arora-Barak 14.1 for a different proof).
Boolean circuits lower bounds: PARITY is not in AC0 (contd), Natural proofs (Arora-Barak 23).
Randomness in computation (Arora-Barak 7.1).
Randomness in computation (Arora-Barak 7.2-7.4).
Randomness in computation (Arora-Barak 7.5).
Interactive proofs (Arora-Barak 8.1-8.2).

Other books:

These books offer different perspective on computational complexity, and you are encouraged to check them out:

Mathematics of the impossible, by Emanuele Viola.

Complexity in computer science, by Thomas Watson.