Reduction from 3SAT to NAE3SAT

846 Views Asked by At

I have seen two reductions -
1. $(x, y, z) => (x, y, a) (a’, z, 0)$
2. 3SAT to NAE4SAT to NAE3SAT

For (2) the initial transform is $(x, y, z) => (x, y, z, a) (x’, y’, z’, a’)$.
This works for $x = y = z = 1$ but not for $x = y = z = 0$. With the latter if $a = 1$, then the NAE4SAT expression is satisfied but the initial 3SAT expression is not.

What is the correct transform for the reduction via NAE4SAT?

1

There are 1 best solutions below

0
On BEST ANSWER

the transform for (2) should be $(x,y,z)=>(x,y,z,a)(x′,y′,z′,a)$. This way even the NAE4SAT is not satisfiable if the initial 3SAT is not satisfiable.