计算复杂性理论的历史

发布网友发布时间：2022-05-12 16:11

共1个回答

热心网友时间：2023-07-22 05:07

在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文On the computational complexity of algorithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n))的概念，并利用对角线法证明了时间层级定理（Time Hierarchy Theorem）。
在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardness of approximation）的研究，以及交互式证明系统（Interactive proof system）理论和零知识证明（Zero-knowledge proof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmic game theory）这一分支。
该领域重要的研究者有（不完全列表）：
史提芬·古克姚期智（Andrew Chi-Chih Yao）Allan BorodinManuel BlumJuris HartmanisRichard KarpLeonid LevinAlexander RazborovMichel SipserAvi WigdersonWalter SavitchRichard StearnsLance FortnowV. ArvindLazlo Ba