計算複雜性理論 计算复杂性理论Computational complexity theory是理论计算机科学和数学的一个分支它致力于将可计算问题根据它们本身的复杂性分类以及将这些类别联系起来一个可计算问题被认为是一个原则上可以用计算机解决的问题亦即这个问题可以用一系列机械的数学步骤解决例如算法 如果一个问题的求解需要相当多的资源无论用什么算法则被认为是难解的计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源时间和空间从而将资源的确定方法正式化了其他复杂性测度同样被运用比如通信量应用于通信复杂性电路中门的数量应用于电路复杂性以及中央处理器的数量应用于并行计算计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制 在理论计算机科学领域与此相关的概念有算法分析和可计算性理论两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题更精确地说它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类相应地在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标后者关心的是何种问题原则上可以用算法解决