<p>Suppose you have variables <span class="math-container">$a,b,t_1,t_2,t_3$</span>.  Consider the formula</p>
<p><span class="math-container">$$\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).$$</span></p>
<p>Notice that every satisfying assignment to this formula has <span class="math-container">$b=\neg a$</span>.  This gives you a gadget to force two variables to be negations of each other.</p>
<p>Now, suppose you have an ordinary 3CNF formula <span class="math-container">$\varphi$</span> on variables <span class="math-container">$x_i$</span>.  For each variable <span class="math-container">$x_i$</span>, add another variable <span class="math-container">$\overline{x}_i$</span> that is forced to be the negation of <span class="math-container">$x_i$</span>.  Now you can rewrite each clause of <span class="math-container">$\varphi$</span> to have the required form.  You take it from here.</p>

CC BY-SA 4.0
2022-03-31T18:34:27.587Z
Alternatively, use Schaefer’s dichotomy theorem.
Emil Jeřábek
CC BY-SA 4.0
2022-03-31T17:38:00.190Z
2022-03-31T17:38:00.190Z
D.W.
<p>We can convert any general <span class="math-container">$3SAT$</span> instance into the instance that has the form described in the question. This will prove that the problem is <span class="math-container">$NP$</span>-Complete, and hence finding a polynomial time algorithm will prove <span class="math-container">$P = NP$</span>.</p>
<p>Let <span class="math-container">$\phi \in 3SAT$</span>. Consider any clause <span class="math-container">$(A \lor B \lor C)$</span> of <span class="math-container">$\phi$</span>. 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:</p>
<ol>
<li><p><span class="math-container">$A = \lnot a$</span>, <span class="math-container">$B = b$</span> and <span class="math-container">$C = c$</span>:<br />
<span class="math-container">$(\lnot a \lor b \lor c) \equiv $</span>
<span class="math-container">$(\tilde{a} \lor b \lor c) \land (\lnot a \lor \lnot \tilde{a} \lor \lnot \tilde{a})$</span>.</p>
</li>
<li><p><span class="math-container">$A = a$</span>, <span class="math-container">$B = \lnot b$</span> and <span class="math-container">$C = \lnot c$</span>:<br />
<span class="math-container">$(\lnot a \lor \lnot b \lor \lnot c) \equiv $</span>
<span class="math-container">$(\tilde{a} \lor b \lor c) \land (\lnot a \lor \lnot \tilde{a} \lor \lnot \tilde{a})$</span>.</p>
</li>
</ol>
<p>In either case, we can easily find an equivalent formula <span class="math-container">$\phi'$</span> for every <span class="math-container">$\phi \in 3SAT$</span> that conforms to the form described in the question, i.e., every clause has either all variables negated, or all variables not negated.
<span class="math-container">$\square$</span></p>

CC BY-SA 4.0
2022-04-01T10:17:34.557Z
2022-04-01T10:17:34.557Z
prime_hit
<p>Given a 3CNF formula <span class="math-container">$\phi$</span> with the condition that, for every clause of <span class="math-container">$\phi$</span>, either all the variables are negated or all the variables are non-negated. For example, some allowed clauses are <span class="math-container">$(x_1\vee x_2\vee x_3)$</span> and <span class="math-container">$(\neg x_1\vee \neg x_2\vee \neg x_3)$</span>. Clause like <span class="math-container">$(x_1\vee \neg x_2\vee x_3)$</span> is not allowed. The question is can we determine efficiently whether <span class="math-container">$\phi$</span> is satisfiable or not.</p>
<p>I tried to solve this by reducing it to the following problem. Two sets of triplets <span class="math-container">$\mathcal{T}_1$</span> and <span class="math-container">$\mathcal{T}_2$</span> are given. All the triplets are subset of a set <span class="math-container">$E$</span>. Then, can we partition <span class="math-container">$E$</span> into two sets <span class="math-container">$E_1$</span> and <span class="math-container">$E_2$</span> such that for every triplet <span class="math-container">$t\in \mathcal{T}_1$</span>, <span class="math-container">$E_1\cap t\neq \emptyset$</span> and for every triplet <span class="math-container">$t\in \mathcal{T}_2$</span>, <span class="math-container">$E_2\cap t\neq \emptyset$</span>. I am stuck at this point.</p>

<ds.algorithms><sat>
Find whether a 3CNF formula with every clause having either all the variables negated or all the variables non-negated is satisfiable
Amritanshu singh
# Find whether a 3CNF formula with every clause having either all the variables negated or all the variables non-negated is satisfiable

(Asked by: username_0 on 2022-03-31)

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.

**Tags:** ds.algorithms, sat

---

## 2 answers

### Answer by username_1 on 2022-03-31. Score: 5

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.

> **Comments:**
> **username_2**: Alternatively, use Schaefer’s dichotomy theorem.  

---

### Answer by username_3 on 2022-04-01. Score: 1

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$


---

