Computability and Complexity
CSE 200

 Place and Time: DIB 121, TTh 11:00am-12:20pm Instructor: Daniel Grier (dgrier@ucsd.edu) TA: Anthony Ostuni (aostuni@ucsd.edu) Resources: Canvas, Gradescope, Piazza Daniel's office hours: Thursday 1pm-2pm and by appointment in CSE 4218 Anthony's office hours: Tuesday 1pm-2pm, Friday 11am-11:55am outside CSE 4232
Assignments
Overview

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, and understand why the "P vs NP" problem is possibly the most important open problem in computer science, mathematics and science at large.

Textbook: Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak
Prerequisites: Undergraduate exposure to algorithms and their analysis, boolean logic, formal language and automata theory, and, most importantly, the ability to read, recognize, and write a valid proof. If you have done well in CSE 105 (Theory of Computation), CSE 101 (Design and Analysis of Algorithms), and CSE 20 (Discrete Mathematics), or equivalent, you should have the necessary background for this course.

Tentative Outline
• Turing machines. Computable functions and robustness under different models.
• Universal TMs. Uncomputable functions. 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 AC^0 (Arora-Barak 14.1).
• 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).