複雜度類之間的關係 下表簡列了一些屬於複雜度理論的問題（或語言、文法等）類別。如果類別X 是類別Y 的子集合 ，則X 將會畫在Y 底下，並以一黑線相連。如果X 是子集合，但不知是否與Y 相等，則以較輕的虛線相連。實際上可解與不可解問題更屬於可計算性理論 ，但是它有助於更透徹了解複雜度類的問題。
擴充閱讀 複雜度類大觀園 （页面存档备份，存于互联网档案馆 ）：一個巨大的複雜度類列表，專家級使用。 ，由Neil Immerman Garey, Michael R. David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP-complete （NPC問題是解決某些數學難題 的重要關鍵，這問題暗示人們是否可以將某些演算法 的執行效率提升到可接受的範圍）問題的標準指南。
参见
复杂性类, 在計算複雜度理論中, 一個複雜度類指的是一群複雜度類似的問題的集合, 一個典型的複雜度類的定義有以下形式, 可以被同一個抽象機器m使用o, 的資源r所解決的問題的集合, n是輸入資料的大小, 例如np類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題, 而p類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題, 某些複雜度類是一群函式問題的集合, 例如fp, 複雜度, 英语, complexity, 許多複雜度類可為數學邏輯所描述刻劃, 請見描述性複雜度, 英语, descriptiv. 在計算複雜度理論中 一個複雜度類指的是一群複雜度類似的問題的集合 一個典型的複雜度類的定義有以下形式 可以被同一個抽象機器M使用O f n 的資源R所解決的問題的集合 n是輸入資料的大小 例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題 而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題 某些複雜度類是一群函式問題的集合 例如FP 複雜度 英语 FP complexity 許多複雜度類可為數學邏輯所描述刻劃 請見描述性複雜度 英语 descriptive complexity 布盧姆複雜度則不需實際抽象機器就可定義複雜度類 複雜度類之間的關係 编辑下表簡列了一些屬於複雜度理論的問題 或語言 文法等 類別 如果類別X是類別Y的子集合 則X將會畫在Y底下 並以一黑線相連 如果X是子集合 但不知是否與Y相等 則以較輕的虛線相連 實際上可解與不可解問題更屬於可計算性理論 但是它有助於更透徹了解複雜度類的問題 決定性問題 類型0 递归可枚举 未決定問題 递归 EXPSPACE NEXPTIME EXPTIME PSPACE 類型1 上下文有关 反NP BQP NP BPP P NC 類型2 上下文无关 類型3 正则 擴充閱讀 编辑複雜度類大觀園 页面存档备份 存于互联网档案馆 一個巨大的複雜度類列表 專家級使用 複雜度類架構圖 由Neil Immerman 英语 Neil Immerman 製作 展示複雜度類的階層架構與它們是如何定位的 Garey Michael R 英语 Michael Garey 與David S Johnson 英语 David S Johnson Computers and Intractability A Guide to the Theory of NP Completeness New York W H Freeman amp Co 1979 NP complete NPC問題是解決某些數學難題的重要關鍵 這問題暗示人們是否可以將某些演算法的執行效率提升到可接受的範圍 問題的標準指南 参见 编辑複雜度類列表 取自 https zh wikipedia org w index php title 复杂性类 amp oldid 67028100, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。