跳转至

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

课程信息

  • 主讲：傅育熙 教授

Info

  • 时间：第 1 至 8 周，每周一、周四下午 18:00 – 20:20 （11 – 13 节）
  • 地点：陈瑞球楼 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)
  2. 交互证明系统 (PDF)

参考教材