复杂性理论(Complexity Theory)
复杂性理论是理论计算机科学和数学的一个分支,它致力于将可计算问题根据它们本身的复杂性分类,以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题,亦即这个问题可以用一系列机械的数学步骤解决,例如算法。
在20世纪50年代,Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来,被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文On the computational complexity of algorithms。在这篇论文中,作者引入了时间在20世纪50年代,Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来,被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文On the computational complexity of algorithms。在这篇论文中,作者引入了时间复杂性类TIME(f(n))的概念,并利用对角线法证明了时间层级定理(Time Hierarchy Theorem)。