CS 505 Computability and Complexity Theory
Spring, 2021
Time and location:
Tuesday and Thursday 2:00-3:15pm, Blackboard Collaborate Ultra
Intructor:
Anastasios Sidiropoulos,
sidiropo@uic.edu,
office hours: TBA
Overview
This course discusses fundametal concepts in compatability and complexity theory. The topics covered include models of computation, undecidability, polynomial-time computation and the classes P and NP, diagonalization, space complexity and the classes PSPACE and NL, the polynomial hierarchy, circuit complexity, randomized computation, interactive proofs, cryptography, quantum computation, and hardness of approximation.
The standard prerequisite course is CS 301 or an equivalent one.
The course will also require general mathematical maturity (i.e. the ability to read and write proofs).
No other special background will be necessary.
Textbooks
Evaluation
There will be one midterm, a final exam, and several homeworks.
The final exam will be comprehensive.
Each homework will be due before the beginning of a predetermined lecture.
No late assignments will be accepted.
The final score is computed using the formula: 0.5 × homeworks + 0.5 × final.
The final letter gades will be curved.
Lectures
-
Jan 12, 2021. Lecture 1: Introduction. Turing machines (Chapter 1).
-
Jan 14, 2019. Lecture 2: Universal Turing machines (Chapter 1).
-
Jan 19, 2019. Lecture 3: Uncomputability (Chapter 1). Time hierarchy (Chapter 3).
-
Jan 21, 2019. Lecture 4: The classes P and NP. Polynomial time reductions, NP-completeness (Chapter 2).
-
Jan 26, 2019. Lecture 5: The Cook-Levin theorem (Chapter 2).
-
Jan 28, 2019. Lecture 6: PSPACE-completeness (Chapter 4).