计算复杂性从可计算性到计算复杂性什么样的问题类是可计算的？这是数学、数理逻辑学和早期计算机科学所关心的一个重要问题

为了回答这个问题，可以给出一个计算的模型，然后规定，凡是这个模型能计算的问题类就叫作可计算的，否则就叫作不可计算的

于是产生了各种计算的模型：图灵机、递归函数、λ 演算、马尔可夫算法和递归算法等

但是，会不会有一类问题，在一个模型中是可计算的，而在另一个模型中却是不可计算的呢？如果这样，一个问题类的可计算性就依赖于模型，而不是问题类本身的性质了

著名的丘奇－图灵论题回答了这个问题

这个论题说：“凡是合理的计算模型都是等价的，即一个模型能算的问题类别的模型也能算，一个模型不能算的别的模型也不能算

”这个论题不是一个严格的命题，无法给于一般的证明，但可以对一个个具体的模型去验证它的正确性

但是，对于一个问题类，只知道它能否计算还很不够，更有实际意义的是要知道计算起来要耗费多少时间，要用多大的空间来存储计算的中间结果等等

为了回答这些进一步的问题，就产生了计算复杂性理论

资源计算时间、存储大小都称为资源

严格地讲，每一种资源的定义都依赖于特定的计算模型

对各种计算模型，资源的定义虽不一样，但主要的可分为三类：① 串行时间（简称时间）：它是计算过程中的总运算量，即把计算分成一些原始的步骤，完成这些步骤所需要的总时间

② 空间：它是为了保存中间结果所需要的存储器的大小

例如在计算时用一块黑板来打草稿，每一单位面积假定可以写一个符号，不用了还可以擦掉

在计算时所需黑板面积就是空间

③ 并行时间：它是并行计算所需要的时间，亦即如果多人或多处理机协同计算，解决一个问题所需要的时间

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。