复杂性类
例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題的集合，例如FP (複雜度)。
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下：
許多複雜度類可被描述它的數學邏輯特徵化，請見可描述的複雜度。
而Blum公理用於不需實際計算模型就可定義複雜度類的情況。
複雜度類之間的關係
下表簡列了一些屬於複雜度理論的問題（或語言、文法等）類別。如果類別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問題是解決某些數學難題的重要關鍵，這問題暗示人們是否可以將某些演算法的執行效率提升到可接受的範圍）問題的標準指南。
参见
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.