<p><strong>Theorem.</strong> No, such a balanced 1-in-3 formula is never satisfiable.</p>
<p><em>Proof.</em> Consider the incidence graph of the formula, which contains an edge <span class="math-container">$(c,x)$</span> when variable <span class="math-container">$x$</span> occurs in clause <span class="math-container">$c$</span>. Say that an edge is <em>satisfying</em> when the variable satisfies the clause, and <em>unsatisfying</em> otherwise. Towards a contradiction, suppose that <span class="math-container">$\vec x\in \{0,1\}^n$</span> is a satisfying assignment. Then each clause is incident to exactly one satisfying edge. Conversely, an edge incident to a variable <span class="math-container">$x_j$</span> with <span class="math-container">$x_j=1$</span> is satisfying iff <span class="math-container">$x_j$</span> occurs positively and unsatisfying if <span class="math-container">$x_j$</span> occurs negatively in a clause. Since the formula is balanced, each variable is therefore incident to the same number of satisfying and unsatisfying edges.</p>
<p>Let us now try to count the number of satisfying edges in the graph via two methods. Say that the formula contains <span class="math-container">$m$</span> clauses and <span class="math-container">$n$</span> variables.</p>
<ol>
<li>There must be <span class="math-container">$m$</span> satisfying edges and <span class="math-container">$2m$</span> unsatisfying ones, since each clause is incident to exactly 1 satisfying edge and 2 unsatisfying edges, and there are <span class="math-container">$m$</span> clauses.</li>
<li>There must be the same number of satisfying and unsatisfying edges, since each variable is incident to the same number of satisfying and unsatisfying edges.</li>
</ol>
<p>Contradiction. <span class="math-container">$\square$</span></p>
<hr />
<p>A slightly more general theorem can be derived using the logic above.</p>
<p>Say that the <em>Discrepancy</em> of a variable <span class="math-container">$x$</span>, is the absolute difference between the number of positive and negative occurrences of that variable in the formula, <span class="math-container">$\Delta(x)=\left|\#\text{positive}_\phi(x) - \#\text{negative}_\phi(x)\right|$</span>. Then the Total discrepancy must be at least <span class="math-container">$\sum_x \Delta(x)\geq m$</span>. Otherwise, the total number of satisfying and unsatisfying edges does not come out right.</p>
<p>Therefore, also slightly unbalanced 1-in-3 formulas can be immediately said to be unsatisfiable. I leave it to you to find out whether this criterion can ever be used to quickly check whether a &quot;normal&quot; 3-CNF formula is satisfiable, using a reduction from 3-CNF SAT to 1-in-3 SAT. (because I don't know ;) ).</p>

CC BY-SA 4.0
2024-09-07T13:51:34.013Z
2024-09-07T13:51:34.013Z
Lieuwe Vinkhuijzen
<p>The variant is the regular 1-in-3SAT problem with only the formulae where each variable and its negation appear the same number of times in the formula.</p>
<p>For example, <span class="math-container">$(a\vee b\vee\neg a)\wedge(\neg a\vee\neg b\vee a)$</span> has each variable appearing the same number of times as its negation. The problem is, given a formula of this type, is there an assignment to the variables s.t. each clause contains exactly 1 satisfied literal.</p>
<p>1-in-3SAT is NP-complete. I wondered if and how one can reduce it to this variant.</p>

<sat><np-complete>
Equal appearance of positive and negative literals in 1-IN-3SAT per variable: Is it NP-complete?
AmirD
# Equal appearance of positive and negative literals in 1-IN-3SAT per variable: Is it NP-complete?

(Asked by: username_0 on 2024-09-06)

The variant is the regular 1-in-3SAT problem with only the formulae where each variable and its negation appear the same number of times in the formula.

For example, $(a\vee b\vee\neg a)\wedge(\neg a\vee\neg b\vee a)$ has each variable appearing the same number of times as its negation. The problem is, given a formula of this type, is there an assignment to the variables s.t. each clause contains exactly 1 satisfied literal.

1-in-3SAT is NP-complete. I wondered if and how one can reduce it to this variant.

**Tags:** sat, np-complete


---

## 1 answers

### Answer by username_1 on 2024-09-07. Score: 4 | Accepted answer

**Theorem.** No, such a balanced 1-in-3 formula is never satisfiable.

*Proof.* Consider the incidence graph of the formula, which contains an edge $(c,x)$ when variable $x$ occurs in clause $c$. Say that an edge is *satisfying* when the variable satisfies the clause, and *unsatisfying* otherwise. Towards a contradiction, suppose that $\vec x\in \{0,1\}^n$ is a satisfying assignment. Then each clause is incident to exactly one satisfying edge. Conversely, an edge incident to a variable $x\_j$ with $x\_j=1$ is satisfying iff $x\_j$ occurs positively and unsatisfying if $x\_j$ occurs negatively in a clause. Since the formula is balanced, each variable is therefore incident to the same number of satisfying and unsatisfying edges.

Let us now try to count the number of satisfying edges in the graph via two methods. Say that the formula contains $m$ clauses and $n$ variables.

1. There must be $m$ satisfying edges and $2m$ unsatisfying ones, since each clause is incident to exactly 1 satisfying edge and 2 unsatisfying edges, and there are $m$ clauses.
2. There must be the same number of satisfying and unsatisfying edges, since each variable is incident to the same number of satisfying and unsatisfying edges.

Contradiction. $\square$

---

A slightly more general theorem can be derived using the logic above.

Say that the *Discrepancy* of a variable $x$, is the absolute difference between the number of positive and negative occurrences of that variable in the formula, $\Delta(x)=\left|\#\text{positive}\_\phi(x) - \#\text{negative}\_\phi(x)\right|$. Then the Total discrepancy must be at least $\sum\_x \Delta(x)\geq m$. Otherwise, the total number of satisfying and unsatisfying edges does not come out right.

Therefore, also slightly unbalanced 1-in-3 formulas can be immediately said to be unsatisfiable. I leave it to you to find out whether this criterion can ever be used to quickly check whether a "normal" 3-CNF formula is satisfiable, using a reduction from 3-CNF SAT to 1-in-3 SAT. (because I don't know ;) ).


---

