1
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .