複雜度類列表

维基媒体列表条目

許多複雜度類都有一個前面加上'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. ^ 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