时间谱系理论

在计算复杂度理论内，时间谱系理论（Time hierarchy theorems）是一个有关图灵机时间限制上面一个重要的理论。用不大正式的说法解释，这理论告诉我们图灵机在给予更多时间之后，保证能解决更多的问题。

简介在计算复杂度理论内，时间谱系理论（Time hierarchy theorems）是一个有关图灵机时间限制上面一个重要的理论。用不大正式的说法解释，这理论告诉我们图灵机在给予更多时间之后，保证能解决更多的问题。

举例：必然存在问题是图灵机可以用n的时间解决，但是不能用n的时间解决。1

计算复杂性理论计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。

如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。

在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。1

图灵机图灵机（英语：Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。1

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学