複雜度類列表

許多複雜度類都有一個前面加上'Co'的同伴，這是包含原來複雜度類裡面所有問題的補集的一個複雜度類。像是，若一個語言屬於NP，則此語言的補集則屬於Co-NP。（注意這裡不代表NP的補集就等同於Co-NP - 有一些語言同時是NP也是Co-NP，也有語言兩者皆非。）

一個複雜度類裡面"最難的問題"代表這個複雜度類裡面所有的問題都可以歸約為這個問題。此外，歸約過程本身是這個複雜度或者比他更簡單的問題類別裡面。

如果找不到想要看的複雜度類（例如說找不到Co-UP），那可以尋找看看這一個類別的同伴（以剛剛的例子來說：UP）來參考。

＃P計算NP問題解答的個數＃P-完全#P問題裡面最難的問題集合2-EXPTIME在雙指數時間內可以解決AC0一個有限制深度的線路複雜度類。AC一種線路複雜度類AH算術階層（arithmetic hierarchy）的複雜度類AP使用交替式圖靈機在多項式時間之內可以解決的問題AM以亞瑟梅林協定在多項式時間內可以解決的問題BPL隨機演算法在多項式時間與對數空間內可以解答的問題集合（解答或許不正確）BPP隨機演算法在多項式時間內可以解答的問題集合（解答或許不正確）BQP量子電腦在多項式時間內可以解答的問題集合（解答或許不正確）反NP使用非決定型圖靈機可以在多項式時間內檢查輸出將為"NO"的問題反NP完全Co-NP問題裡面最難的問題集合DSPACE(f(n))使用決定型圖靈機在O(f(n))空間裡面可以解決的問題DTIME(f(n))使用決定型圖靈機在O(f(n))時間裡面可以解決的問題E可以用指數時間，在線性指數之下，解決的問題ELEMENTARY在指數層級（exponential hierarchy）裡面所有複雜度類的聯集ESPACE可以用指數空間，在線性指數之下，解決的問題EXPEXPTIME的另一種稱呼EXPSPACE在指數大小空間內可以解決的問題EXPTIME在指數大小時間內可以解決的問題FNP相類於NP的功能性問題版本FP相類於P的功能性問題版本FPNPPNP的功能性問題版本，又名NP-易；有名的旅行推銷員問題屬於這一類IP使用交互式證明系統可在多項式時間內解決的問題L可以在對數（小）空間內解決的問題 LOGCFL  可以在對數空間內歸約為上下文無關語言MA使用梅林亞瑟協定在多項式時間內可以解決的問題NC用并行计算机可以有效率（換句話說，在多項式對數時間，polylogarithmic time，之內）解決的問題NE可以用指數時間，在線性指數之下使用非確定型圖靈機解決的問題NESPACE可以用指數空間，在線性指數之下使用非確定型圖靈機解決的問題NEXP NEXPTIME的別名NEXPSPACE使用非決定型圖靈機在指數空間內可以解決的問題NEXPTIME使用非決定型圖靈機在指數時間內可以解決的問題NL正確的解答可以在對數時間內被檢查完畢NONELEMENTARYELEMENTARY的補集NP正確的解答可以在多項式時間內被檢查完畢（參見複雜度類P與NP的關係）NP-完全NP裡面最難的問題集合NP-易（或稱NP-容易）FPNP的別名NP-等價FPNP裡面最難的問題，同時是NP-易也是NP-難的問題NP困难NP-完全或者更難的問題NSPACE(f(n))以O(f(n))這麼多空間使用非決定型圖靈機可以解決的問題NTIME(f(n))以O(f(n))這麼多時間使用非決定型圖靈機可以解決的問題P以多項式時間使用一般圖靈機可以解決的問題P-完全在P複雜度裡面，從并行计算机的角度看，最難解決的一類問題PH在polynomial hierarchy裡面所有類別的聯集PNP使用一個可以解決一種NP問題的神諭，則可以在多項式時間內解決的問題；也叫做Δ2PPP概率多項式時間（答案有稍多於½的機會是正確的）PSPACE在多項式大小的記憶體內可以解決的問題PSPACE-完全PSPACE問題裡面最難的問題R有限時間內可以解決的問題RE若答案為"YES"我們在有限時間內可以知道，但是若答案為"NO"我們可能永遠算不出來的問題RL使用隨機演算法在對數大小空間內可以解決的問題（回答"NO"時有機會出錯，回答"YES"時一定是對的）RP使用隨機演算法在多項式時間內可以解決的問題（回答"NO"時有機會出錯，回答"YES"時一定是對的）UP非模糊非決定型多項式時間的決定性問題ZPP以隨機演算法可以解決的問題（答案永遠正確，平均時間複雜度為多項式時間）

 參考資料 

 外部链接 
 Complexity Zoo - list of over 400 complexity classes and their properties

*
Category:數學列表