Introduction to Computational Complexity
In this course we start from foundational models like Turing machines, and move through classical complexity classes (P, NP, PSPACE, etc.). Topics include reducibility, completeness, and hierarchy theorems. Advanced topics include complexity of counting, randomness, circuit complexity, and interactive proofs.
Lecturer
Date
8th October ~ 31st December, 2024
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Tuesday | 14:20 - 17:50 | A3-2a-201 | ZOOM 01 | 928 682 9093 | BIMSA |
Syllabus
Turing machines and computability.
P, NP, reducibility, NP-completeness, and Cook-Levin theorem.
Time hierarchy theorem, Ladner's theorem.
PSPACE, NL.
\Sigma^p_2, Polynomial hierarchy, time-space tradeoffs.
Boolean circuits: P/poly.
Probabilistic TMs: RP, ZPP, BPP.
Interactive proofs: IP, AM, MIP.
Quantum: BQP.
Approximation: PCP theorems.
Counting: #P, Toda's theorem.
P, NP, reducibility, NP-completeness, and Cook-Levin theorem.
Time hierarchy theorem, Ladner's theorem.
PSPACE, NL.
\Sigma^p_2, Polynomial hierarchy, time-space tradeoffs.
Boolean circuits: P/poly.
Probabilistic TMs: RP, ZPP, BPP.
Interactive proofs: IP, AM, MIP.
Quantum: BQP.
Approximation: PCP theorems.
Counting: #P, Toda's theorem.
Audience
Advanced Undergraduate
, Graduate
Video Public
No
Notes Public
No
Language
Chinese
Lecturer Intro
Hanru Jiang obtained a Ph.D. in computer science and technology from the University of Science and Technology of China in 2019. From 2019 to 2020, he worked as an assistant research fellow at the Quantum Computing Research Center of Pengcheng Laboratory. In 2020, he joined BIMSA as an assistant professor. His main research directions are programming language theory, compiler verification, and programming language aspects in quantum computing. As the main contributor to the concurrent program separation compilation verification work CASCompCert, won the Distinguished Paper Award of PLDI 2019, a top conference in the field of programming languages.