讓我們回到SAT。這個看似簡單的問題的有趣特性是它不僅存在于NP中，而且還是NP完全問題。這里的“完整”一詞與“圖靈完整”中的完整相同。這意味著它是NP中最難的問題之一，但更重要的是這就是NP完全的定義 - NP中任何問題的輸入都可以轉換為SAT的等效輸入，具體如下： 所有 NP 問題 L 都有一個在多項式時間可計算的”還原函數”f： L（x）= SAT（f（x）） 這樣的一個還原函數不能被看成一個編譯器：編譯器是可以將一些編程語言寫的源代碼等價的轉換成另一種編程語言的機器，也就是擁有語義行為的機器語言。因為 SAT 是 NP 完全的，所以這樣一個還原對于任何可能的 NP 問題都是存在的，比如給定一個合適的塊哈希，驗證一筆
比特幣交易是否合法。這里還可以將一筆交易轉換成一個布爾函數的還原函數，因此當且僅當這個交易是合法的時候這個布爾函數就是可滿足的。
版權申明：本內容來自于互聯網，屬第三方匯集推薦平臺。本文的版權歸原作者所有，文章言論不代表鏈門戶的觀點，鏈門戶不承擔任何法律責任。如有侵權請聯系QQ：3341927519進行反饋。
