複雜度類列表
外觀
許多複雜度類都有一個前面加上'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