決定性問題
維基百科,自由的 encyclopedia
在可計算性理論與計算複雜性理論中,決定性問題,亦稱判定問題,(英語:Decision problem)是一個在某些形式系統回答「是」或「否」的問題。
舉例來說,「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是:「給兩個數字 x 與 y,x 是否可以整除 y?」,此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式(decision procedure)。對決定性問題「給兩個數字 x 與 y,x 是否可以整除 y?」決策程式將確定 x 是否整除 y。一種這樣的演算法是長除法,如果餘數為 0,則原決定性問題的答案為「是」,否則為「否」。若某決定性問題可以被一些演算法所解決,則稱此問題可決定(decidable)。
決定性問題與功能性問題(Function problem,或複雜型問題)密切相關,與決定性問題相比,功能性問題的答案內容會複雜許多,並非較簡單的是與非。範例問題:「給予一個正整數x,則哪些數可整除 x?」
另一個與上述兩類問題相關的是最佳化問題(Optimization problem),此問題關心的是尋找特定問題的最佳答案。
計算複雜度的領域中,分類可決定問題的依據在於「此問題有多難被解決」。在此標準下,所謂的「難」是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞歸理論中,非決定性問題由圖靈度決定,指的是一種在任何解答中隱含的不可計算性量詞。
計算性理論的研究集中在決定性問題上。在§ 與函數問題的等價性中,並沒有失去其普遍性。