1
$\begingroup$

Claim: $3SAT \le_p 4NAE $, where reduction $f$ is defined as such: given a 3CNF formula $\varphi$, add to each clause a new literal $z$ (where $z$ is same literal for each clause), and return new formula $f(\varphi)$.

It seemed pretty easy to show that $\varphi\in 3SAT\Rightarrow f(\varphi)\in 4NAE$:

  • If $\varphi \in 3SAT$, then every clause in $\varphi$ contains at least one $T$ literal. In $f(\varphi)$, let the added literal $z=F$. Then every clause in $f(\varphi)$ contains at least one $T$ and one $F$ literal, so $f(\varphi)\in 4NAE$.

Here's where I'm confused: At first, I thought that if $\varphi \notin 3SAT \Rightarrow f(\varphi) \notin 4NAE$.

We know $\varphi \notin 3SAT$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $\varphi$ containing all true literals, then if $f(\varphi)$ adds $z=T$ to each clause, wouldn't $f(\varphi)$ belong to $4NAE$?

On the other hand, I thought of this argument to show that $ f(\varphi)\in 4NAE \Rightarrow \varphi\in 3SAT$:

  • Suppose $f(\varphi)\in 4NAE$, where $x_i$ represents original literals in $\varphi$ and $z$ is added literal from reduction. Let $Y$ represent a satisfying assigment of $f(\varphi)$.

    • If $z=F$, then for any clause $(x_1 \vee x_2 \vee x_3 \vee z)$ in $f(\varphi)$, we know that either $x_1$ or $x_2$ or $x_3$ had to be true. Thus, the original clause $(x_1 \vee x_2 \vee x_3)$ in $\varphi$ would evaluate as true, and so $\varphi$ contains satisfiable assignment.

    • if $z=T$, then for any clause $(x_1 \vee x_2 \vee x_3 \vee z)$ in $f(\varphi)$, we know that either $x_1$ or $x_2$ or $x_3$ had to be false. Now define the assignment $Y '$ to be identical to $Y$ except with every literal negated, and remove all $z$'s. Then $(\bar x_1 \vee \bar x_2 \vee \bar x_3)$ contains at least one true literal. So $Y'$ is a satisfiable assignment of $\varphi $, and $\varphi \in 3SAT$.

Basic logic says if p then q should be equivalent to "if not q then not p". So obviously I'm making some mistakes or assumptions here. I just don't see where.

$\endgroup$
1
$\begingroup$

The error is in this paragraph:

We know $\varphi \notin \mathsf{3SAT}$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $𝜑$ containing all true literals, then if $𝑓(𝜑)$ adds $𝑧=𝑇$ to each clause, wouldn't $𝑓(𝜑)$ belong to $\mathsf{4NAE}$?

Here's your argument, broken into steps:

  1. Suppose $\varphi \notin \mathsf{3SAT}$. Thus, every assignment for $\varphi$ has at least one falsified clause.

  2. Suppose there was some assignment in which each clause contains a falsified literal. Then $f(\varphi) \in \mathsf{4NAE}$, by choosing $z=T$.

I fail to see the contradiction here. Indeed, if there is some assignment in which each clause contains a falsified literal, then if you complement it, you get a satisfying assignment, as you show in your post. This means that if (1) holds, then (2) cannot possibly hold.

You argument is basically saying "what if I had an unsatisfiable $\varphi$ together with an assignment in which each clause contains a falsified literal". If such a $\varphi$ existed, then your reduction wouldn't have been sound. Fortunately, no such $\varphi$ exists. It's true that you have to rule out the existence of such $\varphi$, which you do by showing that if (2) holds then (1) doesn't hold.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.