根據問題解決的難易程度對問題進行分類的理論。如果解決一個問題所需的步驟數受問題規模的某個冪次方限制，則該問題被歸為 P 問題（多項式時間）類。如果一個問題允許非確定性解法，並且驗證解法所需的步驟數受問題規模的某個冪次方限制，則該問題被歸為 NP 問題（非確定性多項式時間）類。P 問題類是 NP 問題類的子集，但也存在不屬於 NP 的問題。
目前還沒有已知的用於圖同構測試的 P 演算法，儘管該問題也尚未被證明是 NP 完全的。事實上，如果 P 和 NP 完全之間存在裂縫，那麼識別同構圖的問題似乎就落在這條裂縫中（Skiena 1990，p. 181），因此，這個問題有時被歸為特殊的圖同構完全複雜性類。
如果已知 NP 問題的解，則可以將其簡化為單個多項式時間驗證。如果一個問題是 NP 問題，並且解決它的演算法可以轉化為解決任何其他 NP 問題的演算法，則該問題是 NP 完全的。NP 完全問題的例子包括哈密頓迴路和旅行商問題。線性規劃曾被認為是 NP 問題，但 L. Khachian 在 1979 年證明它實際上是一個 P 問題。尚不清楚是否所有表面上是 NP 問題的問題實際上都是 P 問題。
參見
位複雜度,
圖同構完全,
NP 完全問題,
NP 難問題,
NP 問題,
P 問題,
P 與 NP 問題
使用 探索
參考文獻
Bridges, D. S. 可計算性。 New York: Springer-Verlag, 1994.Brookshear, J. G. 計算理論：形式語言、自動機和複雜性。 Redwood City, CA: Benjamin/Cummings, 1989.Cooper, S. B.; Slaman, T. A.; and Wainer, S. S. (Eds.). 可計算性、可列舉性、不可解性：遞迴理論的方向。 New York: Cambridge University Press, 1996.Davis, M. 可計算性和不可解性。 New York: Dover, 1982.Du, D.-Z. and Ko, K.-I. 計算複雜性理論。 New York; Wiley, 2000.Garey, M. R. and Johnson, D. S. 計算機與難解性：NP-完全性理論指南。 New York: W. H. Freeman, 1983.
Goetz, P. "Phil Goetz's Complexity Dictionary." http://www.cs.buffalo.edu/~goetz/dict.htmlGriffor, E. R. (Ed.). 可計算性理論手冊。 Amsterdam, Netherlands: Elsevier, 1999.Hopcroft, J. E. and Ullman, J. D. 自動機理論、語言和計算導論。 Reading, MA: Addison-Wesley, 1979.Lewis, H. R. and Papadimitriou, C. H. 計算理論要素，第二版。 Englewood Cliffs, NJ: Prentice-Hall, 1997.Skiena, S. 離散數學實現：組合數學和圖論與 Mathematica。 Reading, MA: Addison-Wesley, 1990.Sudkamp, T. A. 語言和機器：計算機科學理論導論，第二版。 Reading, MA: Addison-Wesley, 1996.Weisstein, E. W. "計算複雜性書籍。" http://www.ericweisstein.com/encyclopedias/books/ComputationalComplexity.html.Welsh, D. J. A. 複雜性：結、著色和計數。 New York: Cambridge University Press, 1993.在 上被引用
複雜性理論
引用為
Weisstein, Eric W. "複雜性理論。" 來自 Web 資源。 https://mathworld.tw/ComplexityTheory.html
主題分類
