计算复杂性高级论题（2024秋）

---

课程信息

• 主讲：傅育熙 教授

致远学院

• 时间：第 1 至 12 周，每周一上午 08:00 – 09:40，每周四上午 10:00 – 11:40
• 地点：东上院 307
• 助教：郑扬珞（邮箱：wunschunreif AT sjtu DOT edu DOT cn）

研究生班（含电院本科生班）

• 时间：第 1 至 12 周，每周一上午 10:00 – 11:40、每周四上午 08:00 – 09:40
• 地点：东上院 101
• 助教：陈蔚骏（邮箱：cwj2018 AT sjtu DOT edu DOT cn）

讲义

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

作业

作业具体要求和提交通道请在 Canvas 系统查看。

• 第一次作业 (PDF，请忽略文件中的日期) (TeX)

  提交截止时间：11月3日晚12点。

• 第二次作业 (PDF，请忽略文件中的日期) (TeX)

  提交截止时间：11月24日晚12点。

• 第三次作业 (PDF，请忽略文件中的日期) (TeX)

  提交截止时间：12月8日晚12点。

参考教材

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