第9章 應對策略三：隨機與參數化#

前兩章的策略在「換取時間」與「放棄最佳性」之間取捨，本章則引進兩個更根本的新維度：隨機性與問題結構。隨機化讓我們用小的失敗機率換取大幅加速，並衍生出 BPP 這個比 P 更寬鬆（但一般認為等價）的效率類別；參數化複雜度則拒絕用「輸入總長度」單一度量難度，轉而問「難度是否只集中在某個小參數上」，從而為許多 NP-hard 問題找到 k 很小時飛快的方法。最後，量子計算為「什麼是可行計算」帶來了顛覆傳統的新視角。