判定問題（decision problem）

判定問題是一種只允許回答「是」或「否」的問題。「91 是質數嗎？」否。「這串清單含有數值 7 嗎？」是或否。「這些會議能全部排開、互不重疊嗎？」是或否。每個實例恰好得到兩種裁決之一。判定問題是最簡單的計算問題，這正是理論家鍾愛它的原因：把答案縮成一個位元，更容易比較不同問題有多難。

形式上，判定問題把所有合法輸入分成兩群：「是」實例（答案為是）與「否」實例。解它就是給每個輸入正確蓋上裁決章。舉例來說，判定問題 PRIME 接受一個整數，恰在它是質數時回答是，所以 7 與 13 是「是」實例，而 8 與 91 是「否」實例。許多更豐富的問題都有一個自然的判定版本：不問「最短路線是什麼？」（最佳化問題），而是問「存在一條短於 100 公里的路線嗎？」——答案只是是或否。

何必把一切縮成是非？因為這給了一個乾淨、統一的方式來衡量難度，而這正是複雜度理論以及著名的 P 類與 NP 類的整個基礎。而且你通常一無所失：如果你能對每個 k 都快速回答判定問題「存在短於 k 的路線嗎？」，你就能用少數幾個這樣的提問釘出真正的最短長度。所以判定問題不是玩具般的限制——它是一個刻意的視角，既讓理論保持鋒利，又仍能觸及我們真正在乎的問題。