複雜度類
基於資源的複雜性相關的計算複雜性理論中的一系列問題
(重定向自复杂性类)
在計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式:
例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題的集合,例如FP (複雜度)。
許多複雜度類可為數學邏輯所描述刻劃,請見描述性複雜度。
複雜度類之間的關係编辑
下表簡列了一些屬於複雜度理論的問題(或語言、文法等)類別。如果類別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問題是解決某些數學難題的重要關鍵,這問題暗示人們是否可以將某些演算法的執行效率提升到可接受的範圍)問題的標準指南。
参见编辑
🔥 Top keywords: Baike: 首页Special:搜索毛泽东家族榮耀之繼承者天之驕女鐵拳英雄九龍城寨之圍城黃循財背着善宰跑篠崎泫妮妃雅新生 (网络剧)劉偉健斯洛伐克习近平劉俊謙 (香港)李显龙歌手2024佛誕淚之女王2024年泰國羽球公開賽新加坡總理邊佑錫新加坡Energy (組合)庆余年九龍寨城六四事件家族榮耀金智媛彌助菲律宾胖猫跳江事件劉寶傑DAY6林峯張文傑李光耀神耆小子張鳳妮黃世聰Seventeen (組合)维基百科願榮光歸香港中華民國鬼滅之刃 柱訓練篇2024年英雄联盟季中邀请赛中华人民共和国TripleS金秀賢 (男演員)罗伯特·菲佐井柏然2024年世界女排联赛黃偉哲怪獸8號佘詩曼Foodpanda金惠奫新加坡总统香緹·摩爾于北辰 (1968年)王嘉爾笑看風雲排球少年!!角色列表林飛帆郭葦昀馴鹿寶貝翁靜晶猩球崛起:王國誕生ILLIT尼古拉·約基奇春色寄情人周殷廷鬼滅之刃排球少年!!吳釗燮逆天奇案2不夠善良的我們BABYMONSTER李正皓尚达曼BOYNEXTDOOR胡子彤IVE (組合)陳靜 (香港)香港吴作栋黃道十二宮凡希亚·奥伊亚胡宇威長洲太平清醮張員瑛搜查班長1958伍允龍习明泽黄岩岛賴清德偶然遇見的你虽然不是英雄