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.
讲师
日期
2024年10月08日 至 12月31日
位置
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| 周二 | 14:20 - 17:50 | A3-2a-201 | ZOOM 01 | 928 682 9093 | BIMSA |
课程大纲
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.
听众
Advanced Undergraduate
, Graduate
视频公开
不公开
笔记公开
不公开
语言
中文
讲师介绍
蒋瀚如于2019年在中国科学技术大学取得计算机科学与技术博士学位，2019-2020年在鹏城实验室量子计算研究中心担任助理研究员，2020年加入BIMSA任助理研究员。他的主要研究方向为程序语言理论、编译器的形式化验证和量子计算中的程序语言问题。作为并发程序分离编译验证工作CASCompCert的主要完成人，获得程序语言领域顶级会议PLDI 2019的Distinguished Paper Award。