复杂性类

维基百科,自由的百科全书
跳转至: 导航搜索

計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式:

可以被同一個抽象機器 M 使用 O(f(n)) 的資源 R 所解決的問題的集合(n是輸入資料的大小)。

例如 NP 類就是一群可以被一非確定型圖靈機多項式時間解決的決定型問題。而 PSPACE 則是一群可以被確定型圖靈機多項式時間解決的決定型問題。某些複雜度類是一群函式問題Function problem)的集合,例如 FP

許多複雜度類可被描述它的數學邏輯mathematical logic)特徵化,請見可描述的複雜度descriptive complexity)。

Blum 公理用於不需實際計算模型就可定義複雜度類的情況。

複雜度類之間的關係[编辑]

下表簡列了一些屬於複雜度理論的問題(或語言、文法等)類別。如果類別X是類別Y子集合,則X將會畫在Y底下,並以一黑線相連。如果X是子集合,但不知是否與Y相等,則以較輕的虛線相連。實際上可解與不可解問題更屬於可計算性理論,但是它有助於更透徹了解複雜度類的問題。

決定性問題
SolidLine.png SolidLine.png
類型 0 (归可枚举)
未決定問題
SolidLine.png
递归
SolidLine.png
EXPSPACE
DottedLine.png
NEXPTIME
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
類型 1 (上下文有关)
DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png
反NP
BQP
NP
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png DottedLine.png
BPP
DottedLine.png
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png
P
SolidLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
SolidLine.png SolidLine.png
類型 2 (上下文无关)
SolidLine.png
類型 3 (正则)

擴充閱讀[编辑]

参见[编辑]