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 :

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 . Let's say where each clause contains three literals : . So, if an expression can be solved with at least two different variable affectations, for each clause, we can have 8 new clauses :

And now, since at least two different affectations must be true, for each clause we can write :

So for each clause, the new number of clauses is 8, so an 3-CNF expression with clauses now has 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