算法复杂性
课程概述¶
由姚鹏晖老师主讲。 历年课程可以在理论组wiki中找到：https://tcs.nju.edu.cn/wiki/index.php?title=Main_Page 笔者认为工作量较大（如果你认真写作业+课程论文的话），个人体验是TCS课程中最难的，课程内容的抽象程度也远大于组合数学和高级算法。
26spring 情况：¶
除了大家耳熟能详的时间复杂性类 \(P\)、\(NP\)、\(coNP\)、\(EXP\) 和 \(NEXP\)，之外，还讲解了 空间复杂性类 \(L\)、\(NL\)、\(coNL\)、\(PSPACE\) 和 \(NPSPACE\)，Polynomial Hierarchy， 电路复杂性类 \(P/poly\)、\(NC\) 和 \(AC⁰\)，随机复杂性类 \(BPP\)、\(RP\)、\(coRP\) 和 \(ZPP\)，交互式证明相关的 \(IP\)、\(MA\)、\(AM\)、\(MIP\) 和 \(PCP\)。最后一节课简单提到了量子复杂性相关内容。
考核与给分¶
与理论组的其他课程一样，不签到。有三次作业（60%）和一个期末论文（40%）。给分与组合数学差不多。