第1章 計算複雜度基礎#

在踏入 NP 問題的世界之前，我們必須先建立一套共同的語言：什麼叫「問題」？什麼叫「演算法」？什麼叫「快」與「慢」？本章將介紹計算複雜度的基本概念，說明為什麼電腦科學家把「多項式時間」當作有效率演算法的分界線，並介紹圖靈機這個最經典的計算模型。這些基礎將貫穿全書，是理解 P、NP、NP-complete 等概念不可或缺的敲門磚。