決定問題（decision problem）

決定問題是任何答案只有「是」或「否」的問題，不會是一個數、一份清單或一張圖，只有兩種裁決之一。這個數是質數嗎？這個圖含三角形嗎？這個程式會停下來嗎？每一個都是決定問題；把問題精簡成單一的是或否答案，正是讓它們乾淨到足以建立統一理論的關鍵。

形式上，決定問題是一個從輸入到 {是, 否} 的函數。因為我們把每個輸入編碼成字串、把「是」的輸入收進一個集合，所以每個決定問題都恰好對應一個語言：所有答案為是的字串構成的語言。解決決定問題就是：對任何輸入字串，正確報出是（字串在語言中）或否（不在）。這正是為什麼決定問題與語言是同一件事的兩種觀點，也是為什麼成員問題是決定問題的通用形式。

為什麼把注意力縮到是非題？因為這個限制幾乎不損失任何重要的東西，卻讓理論變得可處理：大多數最佳化與搜尋問題都有一個難度幾乎相等的決定版本（不問「找出最大的團」，而問「是否存在大小至少為 k 的團？」）。它也讓我們能乾淨地分類難度。若某演算法總是停機並給出正確的是非答案，該決定問題就稱為可判定；若不存在對所有輸入都行得通的這種演算法，則稱為不可判定（停機問題是著名的不可判定例子）。而在可判定問題之中，像 P 與 NP 這樣的複雜度類別再依「需要多少時間或記憶體」進一步分類。