決定性問題(Decision problem)是一個在某些形式系統回答是或決定性問題只有是-否兩種輸出否的問題。
基本介紹
- 中文名：決定性問題
- 外文名：Decision problem
綜述,定義,例子,可決定性,完備性,歷史,等價性,
綜述
在可計算性理論與計算複雜性理論中，所謂的決定性問題(Decision problem)是一個在某些形式系統回答是或決定性問題只有是-否兩種輸出否的問題。例如：“給兩個數字x與y，x是否可以整除y？”便是決定性問題，此問題可回答是或否，且依據其x與y的值。決定性問題在數學問題是否“可決定”中出現，即是否存在有效方法判定一個性質的存在性。數學中許多重要的問題都是不可決定的。
決定性問題與功能性問題(Function problem)（或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是比“與非”複雜很多。範例問題：“給予一個正整數x，則哪些數可整除x？”
另一個與上述兩類問題相關的是最佳化問題，此問題關心的是尋找特定問題的最佳答案。
解決決定性問題的方法稱為決策程式或算法。一個針對決定性問題的算法將說明給予參數x和y的情況下如何決定x是否整除y（就是國小學的長除法）。若是某些決定性問題可以被一些算法所解決，則稱此問題可決定。
計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的算法所花費的計算資源為依據。在遞歸理論中，非決定性問題由圖靈度（不可解度）決定，指的是一種在任何解答中隱含的不可計算性量詞。
計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。
一個判斷決定性的重要手段是萊斯定理(Rice's Theorem)。
定義
決定性問題指的是在一個數量為無限大的輸入集合中，可產出任何是或非解答的問題之集合。因此傳統上定義決定性問題，乃依其解答為是的輸入之集合。在此情形下，一決定性問題亦等於一形式語言。
形式上，決定性問題是一自然數子集A。藉由使用哥德爾數，也可學習諸如形式語言的其他集合。非正規的定義決定性問題，就是判別一個給予的數字是否在此集合內。
例子
一個經典可決定的決定性問題是質數問題。藉由測試每一個可能的因子，有可能有效決定一個自然數是否為質數。儘管存在很多效能更佳的質數判定方法，任何有效方法的存在就已足夠建立可決定性。
在計算複雜性理論中，完備的決定性問題通常用來判別其他決定性問題的複雜度類別。重要的實例包括SAT問題與其數變種，還有無向與有向圖可達性問題。
可決定性
一決定性問題A，若A是一個遞歸集合，則稱做可決定的（decidable）或有效可解（effectively solvable）。若其A是一遞歸可枚舉集合則稱為部分可決定的（partially decidable）、半可決定的（semidecidable）、可解的（solvable）或可證明（provable）。除此之外，此問題稱為不可決定的。
重要的不可決定的決定性問題包括停機問題。
完備性
決定性問題可以利用多至一簡化(Many-one reduction)以及其他相關的簡化如多項式時間簡化(Polynomial-time reduction)來分類。一個決定性問題P被稱為完備的，只要有一個集合包含一組決定性問題S，集合里所有問題都可以簡化為P。完備的決定性問題一般用於計算複雜性理論來分決定性問題於複雜性類。例如布爾可滿足性問題對於決定性問題中的NP問題在多項式時間簡化下是完備的。
歷史
德語“Entscheidungsproblem”，亦即“判定性問題”（Decision-problem），最早出自於大衛·希爾伯特的話：“在1928年的會議上，希爾伯特精確地描述了他的問題。首先，數學是否具有完備性？……其次，數學是否具有相容性？……再次，數學是否具有判定性？這些問題的意思是，是否存在這樣一種確定的方法，在理論上可適用於任何假設，並且能夠保證對無論是否正確的假設都能給出一個正確的結果”（Hodeges，p. 91）。希爾伯特相信“在數學上沒有‘ignorabimus’”，亦即“我們將無從得之”。。
等價性
一個功能性問題是由一個局部函式f組成的，這個非正式的“問題”是計算f在它定義下的值。
所有功能性問題可以轉化成決定性問題；這個決定性問題是這個函式的圖（函式f的圖是指數對(x,y)有f(x)=y）,如果這個決定性問題是可解的，那么這個功能性問題同樣可解。這個簡化沒有考慮計算複雜性，比如劃歸後在多項式時間可決定的函式(運算時間是根據函式(x,y)計算的)不一定在多項式時間內可計算（這時只對x計算），函式f=2^x就有這種性質。
所有決定性問題也能轉換成功能性問題，就是計算決定性問題集合的特徵函式。如果函式是可計算的，那么這個問題就是可決定的。然而，這種轉化比在計算複雜性理論里的轉化（一般叫多至一多項式時間轉化）更加自由。
