Question

Let $\mathit{D}\mathit{O}\mathit{U}\mathit{B}\mathit{L}\mathit{E}\mathbf{-}\mathit{S}\mathit{A}\mathit{T}\mathbf{}\mathbf{=}\{\}\mathbf{}$has at least two satisfying assignments}. Show that$\mathit{D}\mathit{O}\mathit{U}\mathit{B}\mathit{L}\mathit{E}\mathbf{-}\mathit{S}\mathit{A}\mathit{T}\mathbf{}\mathit{i}\mathit{s}\mathit{N}\mathit{P}\mathbf{-}$ complete

Short answer

The$DOUBLE-SAT is NP-complete.$

Step-by-step solution

To proof DOUBLE-SAT∈NP.

$\text{DOUBLE - SAT}\in \text{NP}$

NTM N can decide double-SAT as follows:

Non-deteministicallyguess two Boolean assignments $t_1 and t_2$which are different from each other.

If both $t_1 and t_2$satisfies then accept otherwise, reject.

Hence,$DOUBLE-SAT\in NP.$

Step 2:To Explain DOUBLE-SAT

$SAT{⩽}_{p}DOUBLE-SAT$

The function f which maps an instance D O U B L E-S A T work as follows:

${\varphi }^{\text{'}}=\varphi \wedge \left(x_1\vee x_2\right)$

Where $x_1 and x_2$re new variables. They do not occur in $\phi$.

Thus, the$DOUBLE-SAT$ is NP - complete.