计算复杂性高级论题（2026春）

---

课程信息

主讲：傅育熙 教授

致远学院

• 时间：第 1 至 8 周，每周一、周四晚上 18:00 – 20:20
• 地点：陈瑞球楼 304
• 助教：郑扬珞（邮箱：wunschunreif AT sjtu DOT edu DOT cn）

讲义

1. 课程简介 (PDF)
2. 时间复杂性 (PDF)
3. 空间复杂性 (PDF)
4. NP 完全性 (PDF)
5. 多项式谱系 (PDF)
6. 电路复杂性 (PDF)
7. 随机计算 (PDF)
8. 计数复杂性 (PDF)

---

1. 扩张图与去随机 (PDF)

参考教材

• 《计算复杂性理论》，傅育熙，清华大学出版社，2023.
  • 1 – 15 页 (PDF)
  • 勘误
  • 第 3.6 节（Håstad 对换引理）的更正（PDF）

---

主页由智能体协同维护