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 : $\displaystyle (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 $\displaystyle \wedge$. Let's say $\displaystyle E = C_1 \wedge C_2 \wedge C_3$ where each clause $\displaystyle C_i$ contains three literals : $\displaystyle 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 :

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

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

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

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

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

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

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

$\displaystyle 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 :

$\displaystyle 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 $\displaystyle n$ clauses now has $\displaystyle 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