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

---

课程信息

主讲：傅育熙 教授

致远学院

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

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

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

讲义

1. 课程简介 (PDF)
2. 时间复杂性 (PDF)
3. 空间复杂性 (PDF)

---

作业

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

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

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

参考教材

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