決定問題的表述（decision-problem phrasing）
我們在乎的許多問題要的是一個東西，而非是或否：把這串清單排序、找最短的巡迴、給我最大的匹配。然而複雜度理論建立在「接受或拒絕一個字串」的機器之上，所以它原生的問題是是／否問題。決定問題的表述就是彌合這道鴻溝的訣竅：我們把最佳化或搜尋任務改寫成一個是／否問題，這讓我們能把它當成一個形式語言（答案為「是」的輸入所成的集合），並把它塞進像 P 這樣的類別。
做法是在任務上裝一個目標值或預算，問它能否被達成。「找最短巡迴」變成決定問題「對給定的數 B，是否存在長度至多 B 的巡迴？」。「找最大團」變成「圖中是否含有大小至少 k 的團？」。「找一個可滿足的賦值」變成「是否存在任何可滿足的賦值？」。每個是／否版本對應一個語言，即所有「答案為是」的良構輸入（圖加預算、公式等等）所成的集合，而那正是圖靈機能判定的物件。這就是為什麼在整個複雜度理論裡，你會看到問題以大寫命名為決定問題：SAT、CLIQUE、VERTEX-COVER、HAMILTONIAN-PATH。
兩則安心話讓這個表述無害。第一，決定版本本質上和原問題一樣難：如果你能快速回答「是否存在長度至多 B 的巡迴？」，你通常能藉由對 B 做二分搜尋找出最佳長度，再用幾個額外的決定查詢重建一條實際的最佳巡迴，全都只有多項式額外開銷。所以研究決定問題不會失去本質上的困難度。第二，這純粹是建模上的方便，並非理論的弱化；它只是讓語言、接受、複雜度類別的整套機器，能一致地套用到那些本來不是以是／否問題出生的問題上。
最佳化問題「圖 G 中最大團的大小是多少？」變成決定問題 CLIQUE：「給定 G 與整數 k，G 是否有一個由 k 個兩兩相連頂點組成的團？」。對每個 k 回答這個是／否問題（或對 k 做二分搜尋），就能還原出最佳大小，所以決定版本掌握了完整的困難度。
加上一個預算 k，就把最佳化任務變成一個機器能判定的是／否語言。
決定版本（在多項式額外開銷意義下）和原本的最佳化或搜尋問題一樣難，所以把複雜度理論限縮到是／否問題並未失去本質困難度；這是建模上的方便，而非限制。