重念一次早該補起來的「資料結構與演算法」。這篇筆記 Nondeterministic Turing Machine 其中的 Guessing & Checking。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/30008
本篇範圍：Chapter 13
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Guessing
理論上：若 NP 問題有解，那 NTM 就會在 O(1) 或是 Polynomial 的時間內給出可能的解；若無解，也會給出隨機的錯誤解。不過我們一開始並不會知道 NP 問題是屬於有解還是無解，所以會靠 Checking 的階段來進行驗證
Checking
在 O(1) 和 Polynomial 的時間內，會給出某個解是否正確
