同一個問句的四種形狀
從前面的指南你已經知道，計算問題是一份合約——它說明什麼樣的輸出才算正確，卻不說該怎麼算出來——而且一個問題有無窮多個實例。現在我們再加上第二個同樣有用的視角。拿幾乎任何具體任務來看，你會發現它能用四種不同的方式表述，每種都要求一種不同形狀的答案。心裡先記住一個貫穿全文的例子：一張有城鎮與道路的地圖，任務是「從城鎮 A 走到城鎮 B」。
決定性版本問一個是非問題：「從 A 到 B 存在任何路線嗎？」搜尋版本要你產生一個實際的物件：「給我一條從 A 到 B 的路線（或回報無解）。」最佳化版本要的是依某個度量而言最好的物件：「給我從 A 到 B 最短的路線。」計數版本要的是一個總數：「從 A 到 B 有幾條相異的路線？」同一張地圖，四份真正不同的工作——而答案的型別本身也跟著變，從一個位元，到一條路線，到一條最佳路線，再到一個數字。
決定性與搜尋：一個「是」，與一個見證
決定性問題恰好輸出一個位元。每個合法輸入都被蓋上是或否的章，把所有輸入分成「是」實例與「否」實例。把答案縮成單一位元感覺像在丟棄資訊，確實如此——而且是刻意的。正是這份簡樸，讓理論能在共同的尺度上比較不同問題有多難，而這正是你稍後會遇到的 P 類與 NP 類的整個基礎。「存在一條短於 100 公里的路線嗎？」是一個決定性問題，它的答案就只是是或否。
搜尋問題更為苛刻：它要求一個見證——一個證明答案為是的具體物件。不是「有路線嗎？」而是「把一條路線交給我。」這個見證有個美妙的性質：它通常很容易檢查。把一條聲稱的路線交給某人，他就能一條邊一條邊地走過去，確認它真的連起了 A 與 B。這種可檢查性正是通往驗證器這個概念的橋樑：一份你能快速核驗的簡短證明，即使要找到它很困難。一盤解好的數獨就是見證；核驗它易如反掌；從空格把它生出來才是真功夫。
搜尋至少和決定性一樣難，理由是一句話的論證：如果你能找出一條路線，你當然能回答它是否存在（看看你的搜尋有沒有回傳東西就好）。反向則未必成立——知道路線存在，本身並不告訴你那條路線。然而實務上，我們常透過對答案的片段提決定性問題，把一個決定性神諭轉成一套搜尋程序：「如果我禁用這條路，還有路線嗎？」把答案少了也能存活的道路一條一條移除，最終就會讓一條路線顯露出來。這是一項真實、可重用的技巧，叫做自我歸約——不是免費午餐，卻是強而有力的模式。
最佳化：不只有效，而是最好
最佳化問題把門檻從「一個有效解」提高到「最好的有效解」。它有三個每次都值得點名的部分：可行解（哪些候選根本被允許——這裡是從 A 到 B 的所有路線）、目標（給每個候選打分的數——總距離），以及方向（極小化或極大化）。答案是一個目標值沒有別的可行解能勝過的可行解。把最佳值（最好的分數，比方 42 公里）與最佳解（一條達成它的路線）分開來談會很有幫助；有時你要前者，有時要後者。
最佳化透過一座乾淨的橋連回決定性：每個最佳化問題都有一個自然的決定性版本，「存在一個目標值至多為 k 的可行解嗎？」如果你能對任何門檻 k 都快速回答那個是非問題，那麼對 k 的各個值做一段短短的掃描就能釘出最佳值——對整數目標，你甚至能對 k 做二分搜尋。這座橋被不斷使用：決定性版本的困難結果（「這個是非問題沒有已知的快速演算法」）正是這樣立刻告訴你，最佳化版本也很困難。
計數：有幾個，以及為何它可能是最難的
計數問題問的是解集合的大小：不是「有路線嗎？」，不是「給我一條路線」，而是「究竟有幾條相異的路線？」輸出是單一一個數，而即使每個個別解都很短、很容易描述，它仍可能大到天文數字。數一個 n 元集合的子集，答案乾淨俐落是 2^n；密集地圖中路線的數目也能以同樣的方式爆炸。凡是牽涉總量、平均或機率的地方，計數就很要緊，因為一個機率正是一個計數除以另一個計數。
這裡有個讓新手吃驚的教訓：計數至少和搜尋一樣難，而且往往嚴格地更難。「至少」這個方向很簡單——如果你知道確切的計數，你就知道它是否為零，這免費回答了決定性問題。「嚴格地更難」這個方向才是驚人之處。存在一些問題，找出一個解確實很容易，但把所有解都數清卻被認為難解。所以「就把它們數一數」很少像聽起來那麼天真；總數背後藏著真實的計算難度，而光是答案的大小就暗示了，為何用暴力法逐一列出毫無希望。
一個具體的對比能讓這道鴻溝變得生動。要數方格盤上的解，你通常不能只是逐一列舉它們——數量太多了。你反而要善用結構，常用的是逐格累加部分計數的動態規劃，全程不曾列出哪怕一條完整路線。計數的算術（子計數的和與積）是一具反覆出現的引擎，而這也是第一個提示：一個問題如何表述，決定了哪種設計典範才有機會奏效。
一道難度的階梯，以及為何表述方式很重要
把這四種形狀排成一列，會揭示出同一個底層任務的一道大致的難度階梯。決定性坐在底層（一個位元），搜尋加上了產生見證的負擔，最佳化加上了勝過每一個替代方案的負擔，而計數加上了一次把所有解全部清算的負擔。這道階梯是個指引，不是鐵律——對最短路徑這類簡單問題，四個橫檔都是可解的——但它是個可靠的直覺：如果決定性版本已經很難，更豐富的版本至少一樣難。
- 決定性：輸出一個位元——存在一個可行解嗎？（「從 A 到 B 有路線嗎？」）
- 搜尋：輸出一個見證——產生一個可行解，或回報無解。（「給我一條路線。」）
- 最佳化：輸出一個最佳見證——一個目標值最佳的可行解。（「給我最短的路線。」）
- 計數：輸出一個數——有幾個可行解。（「有幾條相異的路線？」）
為什麼要在碰任何技巧之前，先在表述方式上下功夫？因為問句的形狀，而非它周圍的字句，決定了什麼才算正確答案——也因此決定了哪種設計典範有一線希望奏效。「找出八個皇后互不攻擊的一種擺法」是一個搜尋問題，你會用暴力列舉或回溯法去攻它；「這樣的擺法有幾種？」是一個計數問題，需要不同的機器；「最便宜的巡迴路線是否低於 k？」是一個可能很難的決定性問題。先把形狀釘死，再選你的工具——這整道階梯，某種意義上，就是一份依形狀配對工具的目錄。