在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式：
- 可以被同一個抽象機器 M 使用 O(f(n)) 的資源 R 所解決的問題的集合（n是輸入資料的大小）。
例如 NP 類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而 PSPACE 則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如 FP。
許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。
而 Blum 公理用於不需實際計算模型就可定義複雜度類的情況。
複雜度類之間的關係 [编辑]
下表簡列了一些屬於複雜度理論的問題（或語言、文法等）類別。如果類別X是類別Y的子集合，則X將會畫在Y底下，並以一黑線相連。如果X是子集合，但不知是否與Y相等，則以較輕的虛線相連。實際上可解與不可解問題更屬於可計算性理論，但是它有助於更透徹了解複雜度類的問題。
擴充閱讀 [编辑]
参见 [编辑]
|
|
|
| 易解复杂度类 |
|
|
|
| 怀疑难解复杂度类 |
|
|
| 难解复杂度类 |
|
|
| 复杂度类的谱系 |
|
|
| 相关复杂度族 |
|
|
