決定性問題
Clash Royale CLAN TAG#URR8PPP
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。
決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」
另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。
解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。
計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。
計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。
目录
1 定義
2 例子
3 歷史
4 與函數問題的等價性
5 參考
定義
決定性問題指的是在一個數量為無限大的輸入集合中，可產出任何是或非解答的問題之集合。因此傳統上定義決定性問題，乃依其解答為是的輸入之集合。在此情形下，一決定性問題亦等於一形式語言。
形式上，決定性問題是一自然數子集A。藉由使用哥德尔数，也可學習諸如形式語言的其他集合。非正規的定義決定性問題，就是判別一個給予的數字是否在此集合內。
一決定性問題若其A是一個递归集合，則稱做可決定的（decidable）或有效可解（effectively solvable）。若其A是一递归可枚举集合則稱為部分可決定的（partially decidable）、半可決定的（semidecidable）、可解的（solvable）或可證明（provable）。除此之外，此問題稱為不可決定的。
例子
一個經典可決定的決定性問題是質數問題。藉由測試每一個可能的因數，有可能有效決定一個自然數是否為質數。儘管存在很多效能更佳的質數判定方法，任何有效方法的存在就已足夠建立可決定性。
重要的不可決定的決定性問題包括停機問題，其他請見不可決定的問題列表。在計算複雜性理論中，完備的決定性問題通常用來判別其他決定性問題的複雜度類別。重要的實例包括SAT問題與其數變種，還有無向與有向圖可達性問題。
歷史
德语“Entscheidungsproblem”，亦即“判定性问题”（Decision-problem），最早出自于大衞·希尔伯特的话：“在1928年的会议上，希尔伯特精确地描述了他的问题。首先，数学是否具有完备性？……其次，数学是否具有相容性？……再次，数学是否具有判定性？这些问题的意思是，是否存在这样一种确定的方法，在理论上可适用于任何假设，并且能够保证对无论是否正确的假设都能给出一个正确的结果”（Hodeges，p. 91）。希尔伯特相信“在数学上没有‘ignorabimus’”，亦即“我们将无从得之”。需要了解更多信息请参见大衞·希尔伯特和停机问题。
與函數問題的等價性
參考
Hodges, A., Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for some more history that led to Turing's work.
- Hodges references a biography of David Hilbert: Constance Reid, Hilbert（George Allen & Unwin; Springer-Verlag, 1970）. There are apparently more recent editions.
- Kozen, D.C.（1997）, Automata and Computability, Springer.
- Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
- Sipser, M.（1996）, Introduction to the Theory of Computation, PWS Publishing Co.
- Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7
重要的複雜度類（完整列表） | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 易解复杂度类 |
|  | |||||||
| 怀疑难解复杂度类 |
| ||||||||
| 难解复杂度类 |
| ||||||||
| 复杂度类的谱系 |
| ||||||||
| 相关复杂度族 |
| ||||||||
|