重念一次早該補起來的「資料結構與演算法」。這篇筆記下 NP 完全問題。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：https://hiskio.com/en/courses/572/lectures/30009
本篇範圍：Chapter 13
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
NP 完備問題的條件：
1. 可用暴力破解的演算法，並可在 Polynominal Time 的時間內驗證 -> NP 問題的一種
2. 此演算法可以驗證其他問題
一個 NP 問題，可以轉化成一或多個 NP 完備問題。亦即若你解決了一個 NP 完備問題，你可以反過頭來取解其他的 NP 問題
Cook’s Theorem 是第一個 NP 完備問題。換言之，所有的 NP 問題，都可由 Cook’s Theorem 轉換而得
