复杂性类



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


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

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


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


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



複雜度類之間的關係


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












































































決定性問題
SolidLine.pngSolidLine.png
類型0(递归可枚举)
未決定問題
SolidLine.png
递归
SolidLine.png
EXPSPACE
DottedLine.png
NEXPTIME
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.pngDottedLine.pngDottedLine.pngDottedLine.pngDottedLine.png
類型1(上下文有关)
DottedLine.pngDottedLine.pngDottedLine.pngDottedLine.png
SolidLine.pngDottedLine.pngDottedLine.pngDottedLine.pngDottedLine.png
SolidLine.pngDottedLine.png
反NP
BQP
NP
SolidLine.pngDottedLine.pngDottedLine.pngDottedLine.pngDottedLine.png
SolidLine.pngDottedLine.pngDottedLine.png
BPP
DottedLine.png
SolidLine.pngDottedLine.pngDottedLine.pngDottedLine.pngDottedLine.png
SolidLine.pngDottedLine.png
P
SolidLine.pngDottedLine.pngDottedLine.png
SolidLine.png
NC
SolidLine.pngSolidLine.png
類型2(上下文无关)
SolidLine.png
類型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問題是解決某些數學難題的重要關鍵,這問題暗示人們是否可以將某些演算法的執行效率提升到可接受的範圍)問題的標準指南。


参见


  • 複雜度類列表


Popular posts from this blog

【情報】本週珍珠商品重點:煉金時裝 + 艾港勞工宿舍!!

京昆高速公路

【攻略】陳戈-謝勒汗智慧的古書 (完成)