跳到主要内容
步芽

【极致中配】卡耐基梅隆大学 CMU15-855 计算复杂性理论｜2017年秋季

CMU 15-855 研究生计算复杂性理论课，系统讲授层级定理、电路、交互证明、计数复杂性及电路下界等核心主题。

难度
难度 5/5 — 研究生级计算复杂性理论，涉及大量证明与前沿下界结果，需扎实理论功底
适合人群
计算机理论方向研究生及有志于复杂性研究的高年级本科生
前置要求
计算理论/自动机与可计算性（图灵机、判定问题、P/NP 基础）、离散数学（组合、逻辑、证明技巧）、概率论（用于随机化复杂类与随机限制方法）、线性代数与抽象代数（代数电路、有限域相关内容）
课程规模
29 讲 · 1010播放
在 B 站免费观看 →就这门课提问 →排进我的学习路线

主题覆盖

层级定理电路复杂性随机化复杂类多项式时间层级交互式证明IP=PSPACE计数复杂性#PToda 定理永久式AC0 下界开关引理难度与随机性

课程大纲（29 讲）

  1. P1 · Lecture 1 Course Introduction and Overview: Graduate Complexity56 分钟
  2. P2 · Lecture 2 Hierarchy Theorems(Time, Space, Nondeterministic): Graduate Complexity59 分钟
  3. P3 · Lecture 3 Hopcroft--Paul--Valiant Theorem: Graduate Complexity58 分钟
  4. P4 · Lecture 4 Circuits: Graduate Complexity55 分钟
  5. P5 · Lecture 5 Probabilistic Complexity Classes: Graduate Complexity57 分钟
  6. P6 · Lecture 6 Quasilinear Cook--Levin Theorem: Graduate Complexity55 分钟
  7. P7 · Lecture 7 The Polynomial Time Hierarchy: Graduate Complexity57 分钟
  8. P8 · Lecture 8 Oracles, and the Polynomial Time Hierarchy vs. circuits: Graduate Comp59 分钟
  9. P9 · Improving Kannan's Theorem: Graduate Complexity Lecture 8 bonus material at CMU2 分钟
  10. P10 · Lecture 9 Time/Space Tradeoffs for SAT: Graduate Complexity67 分钟
  11. P11 · Lecture 10 Introduction to Arthur-Merlin classes, MA and AM: Graduate Complexity60 分钟
  12. P12 · Lecture 12 More on constant-round interactive proof systems: Graduate Complexity56 分钟
  13. P13 · Approximate counting: Graduate Complexity Lecture 12 at CMU57 分钟
  14. P14 · Lecture 13 Valiant--Vazirani Theorem, and Exact Counting (#P): Graduate Complexi56 分钟
  15. P15 · Lecture 14 Toda's 1st Theorem and the Permanent: Graduate Complexity57 分钟
  16. P16 · Lecture 15 Algebraic Circuit Complexity: Graduate Complexity58 分钟
  17. P17 · Algebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 post10 分钟
  18. P18 · Lecture 16 Instance Checking and the Permanent: Graduate Complexity58 分钟
  19. P19 · Lecture 17 IP = PSPACE: Graduate Complexity56 分钟
  20. P20 · Lecture 18 Random Restrictions and AC0 Circuit Lower Bounds: Graduate Complexity58 分钟
  21. P21 · Lecture 19 The Switching Lemma: PRST version: Graduate Complexity42 分钟
  22. P22 · Lecture 20 (out of order) Permanent is #P-complete: Graduate Complexity54 分钟
  23. P23 · Lecture 21 Monotone circuit lower bounds: Graduate Complexity61 分钟
  24. P24 · Lecture 22 Razborov--Smolensky lower bounds for AC0[p]: Graduate Complexity51 分钟
  25. P25 · Lecture 23 Toda's 2nd Theorem and lower bounds for uniform ACC: Graduate Complex55 分钟
  26. P26 · Lecture 24 Hardness vs. Randomness I: Graduate Complexity60 分钟
  27. P27 · Lecture 25 Hardness vs. Randomness II: Graduate Complexity57 分钟
  28. P28 · Lecture 26 Hardness amplification: Graduate Complexity57 分钟
  29. P29 · Lecture 27 Ironic complexity: Graduate Complexity59 分钟

本课程卡由 AI 生成，可能存在误差，欢迎反馈。