<blockquote>
  <p><strong>Theorem:</strong> The special case of 1-in-3-SAT where each variable 
  appears an even number of times is NP-hard.</p>
</blockquote>

<p><strong>Proof:</strong> Consider an instance <span class="math-container">$I$</span> of 1-in-3-SAT, and let <span class="math-container">$a_1,\ldots,a_n$</span> 
be an enumeration of the variables in <span class="math-container">$I$</span>. 
Assume that variables <span class="math-container">$a_1,\ldots,a_m$</span> occur an odd number of times,
whereas <span class="math-container">$a_{m+1},\ldots,a_n$</span> occur an even number of times.
Without loss of generality <span class="math-container">$m$</span> is an even number (and otherwise, 
add a new dummy clause with three newly created dummy variables).</p>

<p>From instance <span class="math-container">$I$</span>, we create a new instance <span class="math-container">$I'$</span> of 1-in-3-SAT 
in which every variable occurs an even number of times.
Furthermore, <span class="math-container">$I$</span> is satisfiable if and only if <span class="math-container">$I'$</span> is satisfiable:</p>

<ul>
<li>Instance <span class="math-container">$I'$</span> contains all variables and all clauses of <span class="math-container">$I$</span>.</li>
<li>For every variable <span class="math-container">$a_i$</span>, instance <span class="math-container">$I'$</span> contains a (new)
corresponding variable <span class="math-container">$b_i$</span>.</li>
<li>Furthermore, <span class="math-container">$I'$</span> contains a (new) variable <span class="math-container">$c$</span>.</li>
<li>For every clause <span class="math-container">$a_i,a_j,a_k$</span> in <span class="math-container">$I$</span>, instance <span class="math-container">$I'$</span> contains a new clause <span class="math-container">$\lnot b_i, \lnot b_j,\lnot b_k$</span>.</li>
<li>For <span class="math-container">$i=1,\ldots,m$</span>, instance <span class="math-container">$I'$</span> contains a new clause <span class="math-container">$a_i,b_i,c$</span>.</li>
</ul>

<p>It is easy to check that every variable in <span class="math-container">$I'$</span> occurs in an even
number of clauses. If <span class="math-container">$I'$</span> is satisfiable, then this induces a 
satisfying assignment for <span class="math-container">$I$</span>.</p>

<p>Finally consider a satisfying assignment for <span class="math-container">$I$</span>. 
Use truth values <span class="math-container">$b_i:=\lnot a_i$</span> for <span class="math-container">$1\le i\le n$</span> and <span class="math-container">$c:=$</span>FALSE.
The resulting assignment satisfies all clauses in <span class="math-container">$I'$</span>.</p>

CC BY-SA 4.0
2019-09-11T14:36:25.290Z
This absolutely answers my question and I think it would be unfair to move the goalposts now, so I am happy to accept (I am interested in this question for more general reasons)

However, the problem I am really interested in is the monotone (actually, positive) version of 1-in-3-SAT. If you have any thoughts please let me know.
Christopher Purcell
CC BY-SA 4.0
2019-09-11T13:13:10.883Z
2019-09-11T13:13:10.883Z
Gamow
<h2>Intro</h2>

<p>It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly 3 literals per clause and at most 3 occurrences per variable. I am interested in other restrictions on the number of occurrences per variable.</p>

<p>For a set <span class="math-container">$S$</span> of positive integers, define <span class="math-container">$(k,S)$</span>-SAT to be the satisfiability problem restricted to boolean formulas with exactly <span class="math-container">$k$</span> literals per clause, and the number of occurrences of each variable is in the set <span class="math-container">$S$</span>. For example <span class="math-container">$(3,\{1,2,3,4\})$</span>-SAT is hard, <span class="math-container">$(3,\{1,2,3\})$</span>-SAT is easy.</p>

<h2>Sub-questions</h2>

<p>If <span class="math-container">$k=3$</span> and <span class="math-container">$S$</span> is the even numbers, then you can easily pad an instance of <span class="math-container">$3$</span>-SAT to get an equivalent instance of <span class="math-container">$(3,S)$</span>-SAT. Is there anything known more generally? Is it always hard if <span class="math-container">$S$</span> is infinite? Are there any easy cases for <span class="math-container">$k=3$</span> besides <span class="math-container">$S\subseteq \{1,2,3\}$</span>?</p>

<h2>Main Question</h2>

<p>I am really interested in 1-in-3-SAT restricted to the case where each variable appears an even number of times - the standard reduction from 3-SAT introduces new variables some of which occur an odd number of times. My feeling is that the problem should be NP-hard. Is there a suitable reduction from SAT? Or from normal 1-in-3-SAT? Or perhaps some sort of dichotomy theorem I don't know about that can be applied?</p>

<h2>Edit</h2>

<p>The answer to my question as stated is that the problem is indeed hard, because you can simply copy all clauses of a 1-in-3-SAT instance. I now insist that the clauses should not be repeated (we can efficiently preprocess an instance of SAT so that there are no repeat clauses after all)</p>

CC BY-SA 4.0
2019-09-11T11:05:08.560Z
Take a hard instance $I$ of 1-in-3-SAT, and add a copy of every individual clause.  If a variable occurs $t$-times in $I$, then it occurs $2t$-times in the new instance with the copied clauses.
Gamow
CC BY-SA 4.0
2019-09-11T11:50:33.510Z
@Gamow :facepalm: yes of course.. unfortunately I'm not sure that helps me in my research... perhaps I should insist that clauses aren't repeated? The clauses should be a set, not a multiset... I will edit the question I think.
Christopher Purcell
<cc.complexity-theory><reference-request>
Satisfiability problems with restricted (not bounded) number of occurrences per variable
Christopher Purcell
# Satisfiability problems with restricted (not bounded) number of occurrences per variable

(Asked by: username_0 on 2019-09-11)

## Intro

It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly 3 literals per clause and at most 3 occurrences per variable. I am interested in other restrictions on the number of occurrences per variable.

For a set $S$ of positive integers, define $(k,S)$-SAT to be the satisfiability problem restricted to boolean formulas with exactly $k$ literals per clause, and the number of occurrences of each variable is in the set $S$. For example $(3,\{1,2,3,4\})$-SAT is hard, $(3,\{1,2,3\})$-SAT is easy.

## Sub-questions

If $k=3$ and $S$ is the even numbers, then you can easily pad an instance of $3$-SAT to get an equivalent instance of $(3,S)$-SAT. Is there anything known more generally? Is it always hard if $S$ is infinite? Are there any easy cases for $k=3$ besides $S\subseteq \{1,2,3\}$?

## Main Question

I am really interested in 1-in-3-SAT restricted to the case where each variable appears an even number of times - the standard reduction from 3-SAT introduces new variables some of which occur an odd number of times. My feeling is that the problem should be NP-hard. Is there a suitable reduction from SAT? Or from normal 1-in-3-SAT? Or perhaps some sort of dichotomy theorem I don't know about that can be applied?

## Edit

The answer to my question as stated is that the problem is indeed hard, because you can simply copy all clauses of a 1-in-3-SAT instance. I now insist that the clauses should not be repeated (we can efficiently preprocess an instance of SAT so that there are no repeat clauses after all)

**Tags:** cc.complexity-theory, reference-request

> **Comments:**
> **username_1**: Take a hard instance $I$ of 1-in-3-SAT, and add a copy of every individual clause.  If a variable occurs $t$-times in $I$, then it occurs $2t$-times in the new instance with the copied clauses.  
> **username_0**: @username_1 :facepalm: yes of course.. unfortunately I'm not sure that helps me in my research... perhaps I should insist that clauses aren't repeated? The clauses should be a set, not a multiset... I will edit the question I think.  

---

## 1 answers

### Answer by username_1 on 2019-09-11. Score: 5 | Accepted answer

> **Theorem:** The special case of 1-in-3-SAT where each variable
> appears an even number of times is NP-hard.

**Proof:** Consider an instance $I$ of 1-in-3-SAT, and let $a\_1,\ldots,a\_n$
be an enumeration of the variables in $I$.
Assume that variables $a\_1,\ldots,a\_m$ occur an odd number of times,
whereas $a\_{m+1},\ldots,a\_n$ occur an even number of times.
Without loss of generality $m$ is an even number (and otherwise,
add a new dummy clause with three newly created dummy variables).

From instance $I$, we create a new instance $I'$ of 1-in-3-SAT
in which every variable occurs an even number of times.
Furthermore, $I$ is satisfiable if and only if $I'$ is satisfiable:

* Instance $I'$ contains all variables and all clauses of $I$.
* For every variable $a\_i$, instance $I'$ contains a (new)
  corresponding variable $b\_i$.
* Furthermore, $I'$ contains a (new) variable $c$.
* For every clause $a\_i,a\_j,a\_k$ in $I$, instance $I'$ contains a new clause $\lnot b\_i, \lnot b\_j,\lnot b\_k$.
* For $i=1,\ldots,m$, instance $I'$ contains a new clause $a\_i,b\_i,c$.

It is easy to check that every variable in $I'$ occurs in an even
number of clauses. If $I'$ is satisfiable, then this induces a
satisfying assignment for $I$.

Finally consider a satisfying assignment for $I$.
Use truth values $b\_i:=\lnot a\_i$ for $1\le i\le n$ and $c:=$FALSE.
The resulting assignment satisfies all clauses in $I'$.

> **Comments:**
> **username_0**: This absolutely answers my question and I think it would be unfair to move the goalposts now, so I am happy to accept (I am interested in this question for more general reasons)  However, the problem I am really interested in is the monotone (actually, positive) version of 1-in-3-SAT. If you have any thoughts please let me know.  

---

