1982史提芬·古克 Stephen A.Cook 1971年，在他的論文《The Complexity of Theorem Proving Procedures》提出 了NP-Complete並證明Cook定理。 Cook定理-SAT問題是NP-Complete 的，所有NP問題都可以化約為SAT。 Circuit-SAT 證明方法是將《非決定圖靈機》的每一步 驟，轉化為邏輯式，之後就可以化約為 SAT SAT問題。 3-CNF SAT1982 史提芬 · 古克 Stephen A. Cook ● 1971 年，在他的論文《 The Complexity of Theorem Proving Procedures 》提出 了 NP-Complete 並證明 Cook 定理。 ● Cook 定理 - SAT 問題是 NP-Complete 的，所有 NP 問題都可以化約為 SAT 。 ● 證明方法是將《非決定圖靈機》的每一步 驟，轉化為邏輯式，之後就可以化約為 SAT 問題