為了弄明白這樣一個還原的方法，讓我們先考慮評估多項式的問題。首先，讓我們定義一個由整數常量，變量，加法，減法，乘法和（正確匹配的）括號構成的多項式（類似于布爾函數）。現在讓我們考慮下面的問題： 如果 f 是一個變量都來自于集合 {0, 1} 的多項式，并且其中包含一個零項，那么 PolyZero(f) := 1 現在我們就可以構建出一個從 SAT 到 PolyZero 的還原方法了，同時這也說明了 PolyZero 也是一個 NP 完全問題（驗證它是否屬于 NP 就作為留給你們的練習）。
在一個布爾函數的結構要素上是可以定義一個還原函數 r 的。對于任何布爾函數 f，r(f)的值擁有相同的變量個數，并且當且僅當 r（f）（a 1，..，a k）為0時f（a 1，..，a k）為真，其中true對應于1，false對應于0，并且 r(f) 只假設了來自集合 {0, 1} 的變量值 0 或者 1：
r（x i）：=（1 - x i） r（?f）：=（1 - r（f）） r（（f∧g））：=（1 - （1 - r（f））（1 - r（g））） r（（f∨g））：= r（f）r（g） 有些人可能會假設將 r((f ∧ g)) 定義為 r(f) + r(g)，但是那樣的話多項式的結果就會超出集合 {0, 1} 了。 使用函數 r，((x ∧ y) ∨?x) 被轉換成了 (1 – (1 – (1 – x))(1 – (1 – y))(1 – (1 – x))。 注意，對于 r 來說，每一個替換規則都滿足了之前聲明的目的，因此 r 也正確的實現了還原： 當且僅當r(f) 含有集合 {0, 1} 中的一個 0 時，SAT(f) = PolyZero(r(f)) 或者說 f 是可滿足的
版權申明：本內容來自于互聯網，屬第三方匯集推薦平臺。本文的版權歸原作者所有，文章言論不代表鏈門戶的觀點，鏈門戶不承擔任何法律責任。如有侵權請聯系QQ：3341927519進行反饋。
