複雜度類列表
维基媒体列表条目
許多複雜度類都有一個前面加上'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 | 使用交替式圖靈機在多項式時間之內可以解決的問題[1] |
| AM | 以亞瑟梅林協定在多項式時間內可以解決的問題[1] |
| 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 | 可以用指數空間，在線性指數之下，解決的問題 |
| EXP | EXPTIME的另一種稱呼 |
| EXPSPACE | 在指數大小空間內可以解決的問題 |
| EXPTIME | 在指數大小時間內可以解決的問題 |
| FNP | 相類於NP的功能性問題版本 |
| FP | 相類於P的功能性問題版本 |
| FPNP | PNP的功能性問題版本，又名NP-易；有名的旅行推銷員問題屬於這一類 |
| IP | 使用交互式證明系統可在多項式時間內解決的問題 |
| L | 可以在對數（小）空間內解決的問題 |
| LOGCFL | 可以在對數空間內歸約為上下文無關語言 |
| MA | 使用梅林亞瑟協定在多項式時間內可以解決的問題 |
| NC | 用平行電腦可以有效率（換句話說，在多項式對數時間，polylogarithmic time，之內）解決的問題 |
| NE | 可以用指數時間，在線性指數之下使用非確定型圖靈機解決的問題 |
| NESPACE | 可以用指數空間，在線性指數之下使用非確定型圖靈機解決的問題 |
| NEXP | NEXPTIME的別名 |
| NEXPSPACE | 使用非決定型圖靈機在指數空間內可以解決的問題 |
| NEXPTIME | 使用非決定型圖靈機在指數時間內可以解決的問題 |
| NL | 正確的解答可以在對數時間內被檢查完畢 |
| NONELEMENTARY | ELEMENTARY的補集 |
| 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問題的神諭，則可以在多項式時間內解決的問題；也叫做Δ2P |
| PP | 概率多項式時間（答案有稍多於½的機會是正確的） |
| PSPACE | 在多項式大小的記憶體內可以解決的問題 |
| PSPACE-完全 | PSPACE問題裡面最難的問題 |
| R | 有限時間內可以解決的問題 |
| RE | 若答案為"YES"我們在有限時間內可以知道，但是若答案為"NO"我們可能永遠算不出來的問題 |
| RL | 使用隨機演算法在對數大小空間內可以解決的問題（回答"NO"時有機會出錯，回答"YES"時一定是對的） |
| RP | 使用隨機演算法在多項式時間內可以解決的問題（回答"NO"時有機會出錯，回答"YES"時一定是對的） |
| UP | 非模糊非決定型多項式時間的決定性問題 |
| ZPP | 以隨機演算法可以解決的問題（答案永遠正確，平均時間複雜度為多項式時間） |
參考資料
编辑- ^ 1.0 1.1 Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, 2009, ISBN 978-0521424264
外部链接
编辑- Complexity Zoo - list of over 400 complexity classes and their properties