決定性問題- 维基百科，自由的百科全书
文章推薦指數： 80 %
在可計算性理論與計算複雜性理論中，所謂的決定性問題（亦稱判定問題，Decision problem）是一個在某些形式系統回答是或否的問題。
舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。
另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y 的值可回答是或否。
以演算法形式給出的解決決定性問題的方法稱為決策程式（decision procedure）。
決策程式將對決定性問題「給兩個數字 x 與 y，x 是否可以整除 y？」給出確定 x 是
