Xrthnty

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

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

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

許多複雜度類可被描述它的數學邏輯特徵化，請見可描述的複雜度（英语：descriptive complexity）。

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

複雜度類之間的關係

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

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

擴充閱讀

• 
  複雜度類大觀園：一個巨大的複雜度類列表，專家級使用。


• 
  複雜度類架構圖，由Neil Immerman製作，展示複雜度類的階層架構與它們是如何定位的。


• 
  Michael Garey與David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP-complete（NPC問題是解決某些數學難題的重要關鍵，這問題暗示人們是否可以將某些演算法的執行效率提升到可接受的範圍）問題的標準指南。

参见

• 複雜度類列表

查 论 编 重要的複雜度類（完整列表） 易解复杂度类 对数空间相关 DLOGTIME AC0（英语：AC0） ACC0（英语：ACC0） TC0（英语：TC0） L · FL · SL · NL NC SC PolyL 多项式空间相关 P（P-完全） FP（英语：FP (complexity)） ZPP RP BPP BQP（QMA（英语：QMA） PostBQP（英语：PostBQP） EQP（英语：EQP）） 怀疑难解复杂度类 UP NP（NP完全 NP困难 反NP 反NP完全（英语：co-NP-complete）） FNP（英语：FNP (complexity)）（TFNP（英语：TFNP (complexity)）） PH PP #P（#P-完全（英语：Sharp-P-complete）） PSPACE（PSPACE完全（英语：PSPACE-complete）） 难解复杂度类 EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL 复杂度类的谱系 多项式谱系（英语：Polynomial hierarchy） 指數譜系 Grzegorczyk谱系（英语：Grzegorczyk hierarchy） 算术谱系 相关复杂度族 DTIME NTIME DSPACE（英语：DSPACE） NSPACE 可能性核对证明（英语：Probabilistically checkable proof） 交互式证明系统 量子复杂性理论