为了弄明白这样一个还原的方法，让我们先考虑评估多项式的问题。首先，让我们定义一个由整数常量，变量，加法，减法，乘法和（正确匹配的）括号构成的多项式（类似于布尔函数）。现在让我们考虑下面的问题： 如果 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进行反馈。
