計算複雜性理論

計算複雜性理論是计算理论的一部分，研究計算問題時所需的資源。最常見的資源是時間（要通過多少步才能解決問題）和空間（在解決問題時需要多少記憶體）。其他資源亦可考慮，例如在并行计算中，需要多少并行處理器才能解決問題。

複雜性理論和可能性理論不同，可能性理論的重心在於問題能否解決，不管需要多少資源。

[编辑] 參見

判定問題 

大部分複雜性理論都是處理這類問題

複雜性類別 

擁有相似複雜性的判定問題之集合

P=NP問題 

複雜性理論中的重要問題

[编辑] 著名研究者

• 史提芬·古克
• 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