[科普中国]-结构复杂度理论

在计算复杂度理论内，结构复杂度理论（英语：structural complexity theory)或者简单的结构复杂度（英语：structural complexity)是专门研究复杂度类本身，而非单一问题的可计算性或算法的学问。这理论牵涉到研究各种复杂度类的内部结构以及不同复杂度类之间的关系。

简介这理论的出现，是在解决这类问题中第一个，也仍是最重要的一个问题：P/NP问题时，不断失败的一个结果。许多这方面的研究都基于 P!= NP这个假设，以及一个更深远的推测：多项式时间谱系内的复杂度类个数是无限的。

这个领域的一些主要研究方向有：

各种未解的问题，对复杂度类之间关系所产生的影响。

各种限制资源的归约方式以及相对应的完全语言。

各种对于读取跟储存资料的限制以及使用方法，会对复杂度类产生的影响。1

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

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

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

复杂性类在计算复杂度理论中，一个复杂度类指的是一群复杂度类似的问题的集合。一个典型的复杂度类的定义有以下形式：

可以被同一个抽象机器M使用O(f(n))的资源R所解决的问题的集合（n是输入数据的大小）。

例如NP类别就是一群可以被一非确定型图灵机以多项式时间解决的决定型问题。而P类别则是一群可以被确定型图灵机以多项式时间解决的决定型问题。某些复杂度类是一群函数问题的集合，例如FP。

许多复杂度类可被描述它的数学逻辑特征化，请见可描述的复杂度。

而Blum公理用于不需实际计算模型就可定义复杂度类的情况。1

本词条内容贡献者为:

李航 - 副教授 - 西南大学