计算复杂性理论
计算复杂性理论根据任何算法解决问题所需的时间、内存和其他资源量对问题进行分类，明确区分了哪些问题可以高效解决，哪些问题似乎难以处理。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
计算复杂性理论研究计算问题的内在难度，这种难度通过在图灵机等模型上解决问题所需的资源（主要是运行时间和内存）来衡量，并相应地将问题分组到复杂性类中。
Scope
该领域涵盖时间复杂度和空间复杂度类，例如 P、NP、PSPACE 和多项式层级，NP-完全性理论和多项式时间归约，核心的 P 对 NP 问题，以及结合了随机性、交互和证明的资源受限模型，以及与这些类别相关的层级和难度结果。
Sub-topics
Core questions
- 解决给定问题本质上需要多少时间和内存？
- 哪些问题可以高效解决，哪些问题似乎能抵抗所有高效算法？
- 如何证明问题与复杂性类中最难的成员一样难？
- 随机性、交互或非确定性是否增加了真正的计算能力？
Key theories
- 时间和空间层级定理
- 给定严格更多的时间或空间，机器可以解决严格更多的问题，证明了复杂性类形成了真正的层级，并且某些问题本质上比其他问题更难。
- NP-完全性
- Cook-Levin 定理确定了 NP 中的问题，所有其他 NP 问题都可以归约到这些问题，因此，如果其中任何一个问题有一个高效算法，那么所有这些问题都可以高效解决。
- 资源受限模型
- 添加随机性、交互或交替定义了 BPP、IP 和多项式层级等类别，它们之间的关系使我们对额外资源能带来什么和不能带来什么有了更清晰的认识。
Clinical relevance
复杂性理论通过确认哪些问题存在高效算法，哪些问题是 NP-hard 从而最适合使用启发式或近似方法来指导实践；某些问题假定的难度也支撑了现代密码学，其安全性依赖于被认为计算上不可行的任务。
History
Hartmanis 和 Stearns 于 1965 年通过定义复杂性类和证明层级定理创立了该领域。Cook 和 Levin 在 1971 年左右引入了 NP-完全性，Karp 在 1972 年展示了许多自然问题是完全的，随后的几十年增加了随机、交互和概率可检查证明模型。
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- 可计算性与复杂性之间有什么区别？
- 可计算性询问一个问题是否可以被任何算法解决，而不考虑成本。复杂性假设问题是可解决的，并询问该解决方案在时间和内存方面必须有多昂贵，从而在原则上可解决的问题之间做出更细致的区分。
- NP-完全性在实践中为何重要？
- 当一个问题被证明是 NP-完全时，它就与成千上万个其他问题联系在一起，尽管经过数十年的努力，但仍没有已知的高效算法。这表明寻求快速精确算法可能徒劳无功，而近似、启发式或特殊情况方法才是现实的途径。