第3章 NP類問題#
第 1、2 章我們建立了「有效率 = 多項式時間」的心智模型，並見識了 P 類問題。但世界上還有大量問題——排程、路徑規劃、密碼學、物流最佳化——至今沒有人找到多項式時間演算法。本章將正式定義 NP：不是「不好解的問題」的集合，而是「給了答案就能快速驗證」的問題集合。我們會介紹驗證與搜尋的對偶概念、憑證（certificate）與驗證器（verifier）的形式化定義，最後探討現代數學最著名的未解難題：P 是否等於 NP。
第 1、2 章我們建立了「有效率 = 多項式時間」的心智模型，並見識了 P 類問題。但世界上還有大量問題——排程、路徑規劃、密碼學、物流最佳化——至今沒有人找到多項式時間演算法。本章將正式定義 NP：不是「不好解的問題」的集合，而是「給了答案就能快速驗證」的問題集合。我們會介紹驗證與搜尋的對偶概念、憑證（certificate）與驗證器（verifier）的形式化定義，最後探討現代數學最著名的未解難題：P 是否等於 NP。