写在前面

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

如何学习?

不要沉溺于哲学问题(虽然可以作为兴趣偶尔讨论), 形式科学就要有形式科学该有的样子, 能从公理中得出的问题才是你该思考的问题.

目录 - 基础

目前目录中列出的是我个人至少知道要研究些什么的内容, 实际上这里远不止这么一点, 后续的内容我会在学习完毕相应内容后再补充.

1. 自动机模型
2. 图灵机和可计算性
3. NP完备性
4. 空间复杂性
5. 多项式谱系
6. 电路复杂性I
7. 随机化计算
8. 去随机化
9. 计数复杂度
10. 量子计算
11. 交互证明
12. 密码学
13. PCP定理
14. 通讯复杂度
15. 决策树

目录 - 高级论题

这一部分往往是当下研究的热门问题, 理论尚不完善, 笔记内容也不会详细地证明主要的定理. 要学习这部分内容, 需要自己阅读大量的论文, 并且耗费大量的时间, 同时部分问题涉及的理论背景很深, 总之入坑需谨慎, 但也不要被吓退.

1. 离散和问题

约定

1. 第一个自然数是.

主要参考书目

1. Introduction to the Theory of Computation, Michael Sipser
2. Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak

铭记伟人

艾伦·图灵
约翰·冯·诺伊曼
库尔特·哥德尔
阿隆佐·丘奇