計數問題（counting problem）

計數問題問的是有多少個解，而不是有沒有解、或某個解長什麼樣。「把一美元換成零錢有幾種方式？」「在這個方格盤上，從左上走到右下有幾條路徑？」「這八個皇后有幾種擺法能讓彼此互不攻擊？」輸出是一個數——把所有有效答案點清的總數——而即使每個個別解都容易描述，這個數仍可能大到嚇人。

形式上，計數問題接受某個搜尋問題所定義的可接受解集合，並問它的大小。所以當判定版本問「至少有一個解嗎？」、搜尋版本問「給我一個解」時，計數版本問的是「究竟有幾個解？」。舉個簡單例子，數一個 n 元集合的子集個數，答案乾淨俐落是 2^n；數從 5 個裡選 2 個的方式，答案是 10。這些小例子有漂亮的公式，但一般而言，計數可能比尋找難得多：你或許能很快產生地圖的一種有效著色，卻沒有快速辦法把所有著色都數清。

凡是牽涉機率、平均或總量的地方，計數就很要緊——有利結果數除以可能結果數，正是一個計數除以另一個計數。它也是一堂關於問題如何相互關聯的犀利課程：計數至少和判定一樣難（知道計數，就知道它是否為零，這便回答了判定問題），而且存在一些問題判定容易、計數卻被認為難解。所以「就把它們數一數」很少像聽起來那麼天真；總數背後藏著真實的計算難度。