# Prove that 3SAT-2x is NP-Complete

• July 26th 2013, 12:43 AM
NZAU1984
Prove that 3SAT-2x is NP-Complete
Hi,

I've been trying to think about a problem I have to do as an assignment, but I just don't know how to do it precisely as my head is going in every direction at the same time and I'm not sure anything I'm thinking could be good...

Here's the problem.

The 3SAT-2x language is as follows : 3SAT-2x = {<C> | C is an 3-CNF boolean expression with at least two different variable affectations satisfying it}

3-CNF expressions are like this : $(x_1 \vee x_2 \vee x_3) \wedge (\overline{x_2} \vee x_4 \vee \overline{x_5}) \wedge (...)$

Of course, trying every combination of input variables would be exponential !

So first, we have to prove that 3SAT-2x is in NP. Easy since a certificate is that given a variable affectation, we only need to test the 3-CNF expressions with those values.

But now, we have to reduce a problem already known as NP-Complete to 3SAT-2x, and this, in polynomial time. That's the step I'm stuck on !

I'm thinking of something like this... A 3-CNF expressions are clauses separated with $\wedge$. Let's say $E = C_1 \wedge C_2 \wedge C_3$ where each clause $C_i$ contains three literals : $x_{i,1} \vee x_{i,2} \vee x_{i,3}$. So, if an expression can be solved with at least two different variable affectations, for each clause, we can have 8 new clauses :
$C_{i,1} = x_{i,1} \vee x_{i,2} \vee x_{i,3}$

$C_{i,2} = x_{i,1} \vee x_{i,2} \vee \overline{x_{i,3}}$

$C_{i,3} = x_{i,1} \vee \overline{x_{i,2}} \vee x_{i,3}$

$C_{i,4} = x_{i,1} \vee \overline{x_{i,2}} \vee \overline{x_{i,3}}$

$C_{i,5} = \overline{x_{i,1}} \vee x_{i,2} \vee x_{i,3}$

$C_{i,6} = \overline{x_{i,1}} \vee x_{i,2} \vee \overline{x_{i,3}}$

$C_{i,7} = \overline{x_{i,1}} \vee \overline{x_{i,2}} \vee x_{i,3}$

$C_{i,8} = \overline{x_{i,1}} \vee \overline{x_{i,2}} \vee \overline{x_{i,3}}$

And now, since at least two different affectations must be true, for each clause we can write :
$C_i = (C_{i,1} \wedge C_{i,2}) \vee (C_{i,1} \wedge C_{i,3}) \vee (C_{i,1} \wedge C_{i,4}) \vee ... \vee (C_{i,1} \wedge C_{i,8}) \vee (C_{i,2} \wedge C_{i,3}) \vee ... \vee (C_{i,2} \wedge C_{i,8}) \vee (C_{i,3} \wedge C_{i,4}) \vee ...\vee (C_{i,3} \wedge C_{i,8}) \vee ... \vee (C_{i,7} \wedge C_{i,8})$

So for each clause, the new number of clauses is 8, so an 3-CNF expression with $n$ clauses now has $8n$ clauses, which is not exponentiel.

But now, that form isn't SAT-CNF anymore ! Could I use Morgan's law ?! Not sure as it would return 0 when it is satisfiable ?!

I feel completely lost !

Your help would be greatly appreciated !

Thank you