时间和空间复杂度类
复杂度类根据机器解决决策问题所需的时间或内存将问题分组，将计算组织成从对数空间到指数时间的结构化图景。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
复杂度类是指在给定资源限制内可解决的问题集合，这些资源通常是图灵机作为输入长度函数所使用的时间或工作内存，每种资源都有确定性与非确定性变体。
Scope
本主题涵盖确定性与非确定性时间与空间复杂度类的定义，例如 P、NP、L、NL、PSPACE 和 EXPTIME，区分它们的层次定理，它们之间的包含关系和已知关系，Savitch 定理（关联非确定性与确定性空间），以及表征每个类的完全问题。
Core questions
- 问题如何根据解决所需的时间和内存进行分组？
- 标准复杂度类之间哪些包含关系已知是严格的？
- 非确定性空间与确定性空间有何关系？
- 完全问题在表征一个类中扮演什么角色？
Key theories
- 层次定理
- 随着渐近更多的时间或空间，机器可以判定严格更多的语言，因此时间与空间类形成适当的层次结构，资源不能被浪费而不会丢失问题。
- 萨维奇定理
- 任何可以在非确定性空间中解决的问题，都可以使用该空间平方的确定性空间来解决，因此对于内存而言，与时间的情况不同，非确定性最多只提供适度的优势。
Clinical relevance
将问题归入某个复杂度类可以告诉实践者预期结果：P 类问题可以扩展到大型输入，PSPACE 完全问题（如许多游戏和规划任务）难以高效解决，而复杂度类结构则指导是寻求精确算法、近似算法，还是重新设计问题。
History
Hartmanis 和 Stearns 于 1965 年定义了时间有界类并证明了时间层次定理，奠定了该领域的基础。空间复杂度并行发展，Savitch 于 1970 年提出的定理以及后来 Immerman 和 Szelepcsényi 提出的非确定性空间在补运算下的封闭性等结果完善了这一理论。
Key figures
- Juris Hartmanis
- Richard Stearns
- Walter Savitch
- Stephen Cook
Related topics
Seminal works
- hartmanisStearns1965
- savitch1970
Frequently asked questions
- 时间复杂度和空间复杂度有什么区别？
- 时间复杂度计算算法执行的步数，而空间复杂度衡量其使用的内存。它们的行为不同：空间可以在计算过程中重复使用，这就是为什么非确定性空间相对于确定性空间的强大程度远低于时间上的类似比较。
- 层次定理为何重要？
- 它们证明了更多的资源确实允许解决更多的问题，排除了所有类都合并为一个的可能性。这保证了，例如，存在可以在指数时间内解决但不能在多项式时间内解决的问题，从而支撑了整个复杂度类体系。