Introduction to Computational Complexity (Fall 2023)

Jan 1, 0001

Course Number: COMS 4236
Date/Time: MW 1:10-2:25pm
Room: Mudd 524
First meeting: September 6

Syllabus

This Week’s Office Hours (updated every Sunday)

Description

Many computational problems(such as multiplying two numbers, or sorting a list of numbers) are known to be “easy” in the sense that we have efficient algorithms for them. Unfortunately, many other computational problems of great importance (such as factoring large numbers, or finding the shortest tour that passes through all the cities on a map) seem to be difficult. Are these problems really inherently difficult – do no efficient algorithms exist, or do we just need to come up with cleverer algorithms that can solve these problems efficiently?

Questions such as these lie at the heart of computational complexity, which is the study of inherent abilities and limitations of efficient computation. Computational complexity is one of the most fundamental and important topics in computer science; indeed, the core question of computational complexity theory (P vs NP) is one of the most famous and important open questions in all of computer science and mathematics.

Tentative list of topics: time and space complexity, nondeterminism, Cook-Levin, Ladner’s theorem, Polynomial Hierarchy, Nonuniformity, Relativization, Time-Hierarchy Theorems, Savitch’s theorem PSPACE-Completeness, randomized computation, counting complexity, interactive proofs, PCP theorem and the hardness of approximation, meta-complexity.

Problem Sets

All problem sets will be available on this Overleaf [link]: All solutions must be submitted on Gradescope.

  1. Pset0, due September 13.
  2. Pset1, due September 27.
  3. Pset2, due October 11.

Schedule

All Zoom recordings are on CourseWorks

  1. Week 1
    • September 6. Intro to complexity, course overview, computational problems and computational models. [Slides]
    • Helpful reading: Arora-Barak Ch. 1, Sipser Ch. 3.
  2. Week 2
    • Helpful reading: Arora-Barak Ch. 1, 2, Sipser Ch. 3, 7.
    • September 11. Time, space, nondeterminism, P, NP. [Slides]
    • September 13. Co-classes, reductions, NP completeness. [Slides]
  3. Week 3
    • Helpful reading: Arora-Barak Ch. 2, 3.
    • September 18. Cook-Levin, Diagonalization, Time Hierarchy Theorem. [Slides]
    • September 20. Time, Space, Non-deterministic Hierarchy Theorems. [Slides]
  4. Week 4
    • Helpful reading: Arora-Barak Ch 3, 5.
    • September 25. Oracles and Baker-Gill-Solovay. [Slides]
    • September 27. Polynomial Hierarchy. [Slides]
  5. Week 5
    • October 2.
    • October 4.
  6. Week 6
    • October 9.
    • October 11.
  7. Week 7
    • October 16.
    • October 18.
  8. Week 8
    • October 23.
    • October 25.
  9. Week 9
    • October 30.
    • November 1.
  10. Week 10
    • November 8.
  11. Week 11
    • November 13.
    • November 15.
  12. Week 12
    • November 20.
  13. Week 13
    • November 27.
    • November 29.
  14. Week 14
    • December 4.
    • December 6.