搜尋問題（search problem）

搜尋問題要你找出並回傳一個實際的解，而不只是說它是否存在。判定問題對「這堆乾草裡有針嗎？」回答是或否，與之對應的搜尋問題則說「如果有針，把它交給我。」「在這串清單裡找出等於 7 的值（並告訴我位置）」是搜尋問題；「找出這些會議互不重疊的一種安排」是搜尋問題。輸出是一個見證——一個證明答案為是的具體物件。

更精確地說，搜尋問題對每個輸入界定一組可接受的解，並要求演算法產生其中之一（或回報無解）。以邏輯公式的可滿足性為例：判定版本問「這些子句能同時為真嗎？」；搜尋版本問「給我一組對變數的真假指派，使它們全為真。」回傳的指派很容易檢查——代進去看看就好——這正是它之所以是見證的原因。注意搜尋問題至少和判定問題一樣難：如果你能找出一個解，你當然能回答它是否存在，但知道存在卻未必告訴你怎麼找。

搜尋問題才是多數真實應用真正想要的。一個只告訴你「是，存在一條短路線」卻不把它秀出來的路線規劃器毫無用處；你要的是路線。常見的做法是把一個快速的決定程序，透過對答案的片段提判定問題（「第一步必須往北嗎？」）拔升成搜尋程序，但這是一項真本領，不是免費午餐，也正是為什麼「判定」與「搜尋」之間的關係被仔細研究。