计算复杂性理论

计算复杂性理论 （正體）

计算复杂度理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源。最常见的资源是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。

时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。

复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。

参见

Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP-complete in this case was established by Ladner.^[1]

1. ^ Ladner, Richard E.（1975年）．On the structure of polynomial time reducibility(PDF)．Journal of the ACM (JACM)，22：151–171．doi:10.1145/321864.321877． 

判定问题 

大部分复杂度理论都是处理这类问题

复杂度类别 

拥有相似复杂度的判定问题之集合

P=NP问题 

复杂度理论中的重要问题

著名研究者

• 史提芬·古克
• 姚期智 （Andrew Chi-Chih Yao）
• Allan Borodin
• Manuel Blum
• Juris Hartmanis
• Richard Karp
• Leonid Levin
• Alexander Razborov
• Michel Sipser
• Avi Wigderson
• Walter Savitch
• Richard Stearns
• Lance Fortnow
• V. Arvind
• Lazlo Babai

外部链接

• 〈未来数学家的挑战〉，杨照昆、杨重骏
• The Complexity Zoo

stock | retire | vm
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History