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