历史匿名回执 ·
课程内容：时间复杂性、空间复杂性、NP 完全性、多项式谱系、电路复杂性、随机计算、计数复杂性。交互式证明系统稍微讲了一点。 上课自由度：高。有一节课甚至 0 人出现，教室进行了彻底的赛博休假。 考核标准：4 次作业 40，考试 50，似乎送了 10 分。今年没有透题，但考试非常温和，温和得像泡温泉。作业每次选 5 题做，可以选简单的，属于老师把自助餐摆好随便吃的程度。 授课质量：高。就是 slides 里面有些 typo，Toda 定理的证明问题比较大。计算复杂性的证明非常神秘，几乎都是构造性的，需要用心感受，感受的过程基本等同于闭眼摸黑走迷宫。