写在前面

该笔记是我学习计算复杂性课程以及阅读相关书籍的过程中整理的笔记及个人理解. 整理成笔记除了加深我的个人理解外, 在这里分享给大家, 一方面也是是希望更多人能够理解这些内容, 感受这个世界为我们准备的惊喜. 另一方面也是为现在或是将来准备学习计算机的同学展示他们或许没有接触到的计算机科学的一角, 让大家知道计算机科学内涵的深度和广度, 能够看到Coding以外其他的东西, 也许能改变他们以后的人生路径. 注意, 本文不能替代任何课程, 教材或论文, 想要真正学习计算复杂性知识, 还是需要通过正规途径学习. 除此之外, 计算复杂性是密码学等一系列计算机理论课程的基础, 想要从事计算机理论方面的研究, 该课程是技能树上必点的技能.

Thanks to Prof. Fu (Yuxi Fu) at SJTU for giving us wonderful lectures.