跳转至

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

课程信息

主讲：傅育熙 教授

上课时间

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

课程作业

请完成课程教材第四章练习（第23题开始）、第五章练习、第六章练习。

解答须提交PDF文件至canvas系统，我们在latex.sjtu.edu.cn上提供了一个模板供参考。

讲义

  1. 课程简介 (PDF)
  2. 时间复杂性 (PDF)
  3. 空间复杂性 (PDF)
  4. NP 完全性 (PDF)
  5. 多项式谱系 (PDF)
  6. 电路复杂性 (PDF)
  7. 随机计算 (PDF)
  8. 计数复杂性 (PDF)
  1. 扩张图与去随机 (PDF)
  2. 交互证明系统 (PDF)
  3. PCP定理 (PDF)

参考教材