11.5

Let SAT be the usual satisfiability problem and let Double-SAT be the language “a CNF formula has at least two different satisfying assignments”. We give a polynomial-time reduction R from SAT to Double-SAT.

Construction. Given a CNF formula [math]\varphi(v_1,\dots ,v_n)[/math] introduce a fresh variable [math]z[/math] and output [math]\displaystyle{\varphi' = \varphi\;\land\;(z\lor\lnot z)}[/math]. The extra clause [math](z\lor\lnot z)[/math] is a tautology, so the reduction is computed in linear time.

Correctness. 1. If [math]\varphi[/math] is unsatisfiable, no assignment satisfies [math]\varphi'[/math], so     [math]\varphi'[/math] ∉ Double-SAT. 2. If [math]\varphi[/math] is satisfiable, pick any satisfying assignment α to its original variables. Setting [math]z = \text{T}[/math] yields one satisfying assignment for [math]\varphi'[/math], and changing only the value of [math]z[/math] to [math]\text{F}[/math] gives a second, distinct one. Hence [math]\varphi'[/math] has at least two satisfying assignments and lies in Double-SAT.

Because [math]\varphi[/math] is satisfiable ⇔ [math]\varphi'[/math] has ≥2 satisfying assignments, the reduction preserves YES/NO answers. Therefore a solver for Double-SAT could decide SAT; i.e. Double-SAT is NP-hard. (It is also in NP, so it is NP-complete.)

R(φ): // polynomial-time reduction introduce fresh variable z return φ ∧ (z ∨ ¬z)

Back to Chapter 11