第6章 化約的實作#
第四章介紹了化約的理論觀念，本章則要「捲起袖子」實際動手：把 3-SAT 一步步轉成子集合加總、把子集合加總轉成背包與分割、把 3-SAT 轉成圖著色。這些轉換在教科書中常以數學符號一筆帶過，但唯有親自用程式實作、構造出實例並驗證「解一一對應」，才能真正理解化約的本質：它是一個保持解的多項式時間翻譯器。學完本章，你將擁有一套可執行的化約工具箱，也能明白為什麼證明一個新問題 NP-hard 時，選對源頭問題如此重要。
第四章介紹了化約的理論觀念，本章則要「捲起袖子」實際動手：把 3-SAT 一步步轉成子集合加總、把子集合加總轉成背包與分割、把 3-SAT 轉成圖著色。這些轉換在教科書中常以數學符號一筆帶過，但唯有親自用程式實作、構造出實例並驗證「解一一對應」，才能真正理解化約的本質：它是一個保持解的多項式時間翻譯器。學完本章，你將擁有一套可執行的化約工具箱，也能明白為什麼證明一個新問題 NP-hard 時，選對源頭問題如此重要。