For given reduction f, can show "if f(x) in 4NAE then x in 3SAT", but not "if x is not in 3SAT then f(x) not in 4NAE"

Question

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.

Answer 1

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.