Find whether a 3CNF formula with every clause having either all the variables negated or all the variables non-negated is satisfiable

Question

Given a 3CNF formula $\phi$ with the condition that, for every clause of $\phi$, either all the variables are negated or all the variables are non-negated. For example, some allowed clauses are $(x_1\vee x_2\vee x_3)$ and $(\neg x_1\vee \neg x_2\vee \neg x_3)$. Clause like $(x_1\vee \neg x_2\vee x_3)$ is not allowed. The question is can we determine efficiently whether $\phi$ is satisfiable or not.

I tried to solve this by reducing it to the following problem. Two sets of triplets $\mathcal{T}_1$ and $\mathcal{T}_2$ are given. All the triplets are subset of a set $E$. Then, can we partition $E$ into two sets $E_1$ and $E_2$ such that for every triplet $t\in \mathcal{T}_1$, $E_1\cap t\neq \emptyset$ and for every triplet $t\in \mathcal{T}_2$, $E_2\cap t\neq \emptyset$. I am stuck at this point.

Answer 1

Suppose you have variables $a,b,t_1,t_2,t_3$. Consider the formula

$$\bigwedge_i (a \lor b \lor t_i) \land (\neg a \lor \neg b \lor \neg t_i) \land (t_1 \lor t_2 \lor t_3) \land (\neg t_1 \lor \neg t_2 \lor \neg t_3).$$

Notice that every satisfying assignment to this formula has $b=\neg a$. This gives you a gadget to force two variables to be negations of each other.

Now, suppose you have an ordinary 3CNF formula $\varphi$ on variables $x_i$. For each variable $x_i$, add another variable $\overline{x}_i$ that is forced to be the negation of $x_i$. Now you can rewrite each clause of $\varphi$ to have the required form. You take it from here.

Answer 2

We can convert any general $3SAT$ instance into the instance that has the form described in the question. This will prove that the problem is $NP$-Complete, and hence finding a polynomial time algorithm will prove $P = NP$.

Let $\phi \in 3SAT$. Consider any clause $(A \lor B \lor C)$ of $\phi$. If either all the variables are negated, or all the variables are not negated, then we are done, and we leave the clause as it is. The case we need to consider is when one is negated, and the other two are not, or vice versa. WLOG, we consider the following two cases:

1. $A = \lnot a$, $B = b$ and $C = c$:
   $(\lnot a \lor b \lor c) \equiv $ $(\tilde{a} \lor b \lor c) \land (\lnot a \lor \lnot \tilde{a} \lor \lnot \tilde{a})$.

2. $A = a$, $B = \lnot b$ and $C = \lnot c$:
   $(\lnot a \lor \lnot b \lor \lnot c) \equiv $ $(\tilde{a} \lor b \lor c) \land (\lnot a \lor \lnot \tilde{a} \lor \lnot \tilde{a})$.

In either case, we can easily find an equivalent formula $\phi'$ for every $\phi \in 3SAT$ that conforms to the form described in the question, i.e., every clause has either all variables negated, or all variables not negated. $\square$