How do I reduce 3-SAT to a 3-SAT NAE problem?

Question

I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem.

Not only that, I also figure out that I am not so sure about the reduction to 3SAT either.

Anyway, how do I go for that?

Since the size of each clause is already the same, I don't have to work on that. But I can't seem to find a way to create an instance I2 of 3SAT-NAE which is accepted iff the 3SAT accepts it.

EXTRA QUESTION: Does SAT (or 3SAT) allow any operation in the clauses? Because I always saw V (or) and never other operations. That confuses me a lot, because if it only allows V, then I don't get the reduction I found; but if it accepts even AND, then I get it.

Answer 1

For the pedantic's sake, we first have a polynomial reduction $3SAT \leq_p s3SAT$, where the later has strictly 3 terms per clause, not less (as accepted by the former). This is achieved by taking an instance of $3SAT$ and mapping the clauses respectively:

$ (a) \mapsto (\lnot s \lor \lnot s \lor \lnot s) \land (s \lor s \lor a) $

$ (a \lor b) \mapsto (\lnot s \lor \lnot s \lor \lnot s) \land (s \lor b \lor a) $

where $s$ is a dummy variable, and a and b are terms where $\lnot \lnot$ is negated respectively. We concatenate the end result with $\land$. Clearly we construct in polynomial time.

Next we do the polynomial reduction $s3SAT \leq_p NAE-4SAT$, where the second is simply $NAE-3SAT$ but with four terms per clause. For this we take an instance of $s3SAT$ and map each clause as follows:

$ (x \lor y \lor z) \mapsto (x \lor y \lor z \lor s) \land (\lnot x \lor \lnot y \lor \lnot z \lor \lnot s)$

Where $x,y,z$ are terms and $s$ is our dummy variable, as before. Notice the symmetry here, if we find an assignment with $s = true$ we can simply invert the assignment to receive another valid assignment with $s=false$. This is the assignment we want.

As a last step we reduce $NAE-4SAT \leq_p NAE-3SAT$. Take an instance in $NAE-4SAT$ and map the clauses as follows:

$ (a \lor b \lor c \lor d) \mapsto (s \lor a \lor b) \land (\lnot s \lor c \lor d)$

All the same as before, concatenate the result once more. Notice here that if the true and false variable's (one of each must exist) are mapped to the same clause, $s$ can be choose appropriately. If they are mapped to different clauses, $s$ can be choose opposite to the respective variable value in each pair.

To summarize: $3SAT \leq_p s3-SAT \leq_p NAE_4SAT \leq_p NAE-3SAT$.

Answer to extra question: 3SAT only allows $\lor$ in the clauses.

Answer 2

A more straightforward solution is the following:

for each clause add a new variable ci and perform the following transformation.

$(x1 ∨ x2 ∨ x3) \rightarrow (x1 ∨ x2 ∨ ci) ∧ (x3 ∨ \lnot ci ∨ F)$

Where F is the constant value false.

If $(x1 ∨ x2 ∨ x3)$ has a solution where all literals evaluate to true then set ci to false and $(x1∨ x2 ∨ ci) ∧ (x3 ∨ \lnot ci ∨ F)$ is also satisfied with the added condition of "Not-All-Equal".

If $(x1 ∨ x2 ∨ x3)$ has no solution (all literals evaluate to false) then there is no assignment of ci that can make $(x1∨ x2 ∨ ci) ∧ (x3 ∨ \lnot ci ∨ F)$ true.

If $(x1 ∨ x2 ∨ x3)$ has a solution where not all literals evaluate to true then we can always set ci so that $(x1∨ x2 ∨ ci) ∧ (x3 ∨ \lnot ci ∨ F)$ is satisfied.

some examples for the last case:

• if $x1=x2=t \land x3=f$ set ci=f.
• if $x1=x3=t \land x2=f$ set ci=t.

...