博主正在学习INTRODUCTION TO THE THEORY OF COMPUTATION (Second Edition) --Michal Sipser，以及学习“计算复杂性”课程，做一些笔记供自己回忆，如有错误请指正。整理成一个系列计算理论，方便检索。
核心问题
计算理论领域有三个核心问题：
- 自动机 Automata
- 可计算性 Computability
- 复杂性 Complexity
可计算理论和复杂性理论相关性很强closely related。
以上三部分可以由一个问题联结在一起：计算机的限制和基本能力是什么？what are the fundamental capabilities and limitations of computers?
自动机
自动机是处理一些计算的数学模型的定义和性质。其中有两个模型比较常见：finite automaton和context-free grammar。
可计算理论
可计算理论区分哪些问题是可解决的，哪些问题是不可解决的（非多项式时间）。In computability theory, the classification of problems is by those that are solvable and those that are not.
复杂性理论
复杂性理论将问题分为简单的和困难的（非多项式时间）。In complexity theory, the objective is to classify problems as easy ones and hard ones.
证明的类型
type of proof：
- 构造证明 proof by construction
- 反证 proof by contradiction
- 归纳法 proof by induction
版权声明：本文为qq_41545715原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。