<p><strong>Edit:</strong> This answers a related problem, in which &quot;as simple as possible&quot; means that the number of clauses is minimal.</p>
<p>Let <span class="math-container">$A$</span> be the given 3SAT instance. I will assume that you are looking for a corresponding 1-in-3SAT instance <span class="math-container">$B$</span> with as few clauses as possible, rather than some local minimum.
It also seems that you restrict yourself to instances <span class="math-container">$B$</span> whose variables include those of <span class="math-container">$A$</span>, plus potentially new variables, and that any satisfying assignment for <span class="math-container">$B$</span> is also a satisfying assignment for <span class="math-container">$A$</span>, and that any satisfying assignment for <span class="math-container">$A$</span> can be extended to a satisfying assignment for <span class="math-container">$B$</span> using some assignment for the new variables.</p>
<p>Let <span class="math-container">$c$</span> be the number of clauses in <span class="math-container">$B$</span>.
If <span class="math-container">$A$</span> is not satisfiable, then <span class="math-container">$B$</span> will be an unsatisfiable 1-in-3SAT instance of constant length (<span class="math-container">$c=1$</span> or <span class="math-container">$c=2$</span> depending on whether a single clause can contain a literal and its negation).</p>
<p>We can in polynomial time tell whether <span class="math-container">$A$</span> is satisfiable based on <span class="math-container">$B$</span> as follows.
If <span class="math-container">$c&gt;2$</span>, then <span class="math-container">$A$</span> is satisfiable.
If <span class="math-container">$B$</span> has length <span class="math-container">$c$</span>, we can find all its satisfying assignments in <span class="math-container">$O(c2^{3c})$</span> time, so if <span class="math-container">$c\leq 2$</span>, we can find all satisfying assignments in constant time and hence determine whether <span class="math-container">$A$</span> is satisfiable.
Therefore, a reduction to a 1-in-3SAT instance with a minimum number of clauses is NP-hard.</p>

CC BY-SA 4.0
2021-09-07T04:54:51.810Z
we don't know if the instance is satisfiable, has a unique solution or more than one solution. I am simply trying to find a reduction from SAT to 1-in-3-SAT but with a couple of additional constraints. I am afraid that this simply does not answer my query! we are not trying to solve the problem but a general reduction without caring about the number of solutions.
J.Doe
CC BY-SA 4.0
2021-09-07T07:17:42.273Z
The point is that any reduction will be able to determine whether an instance is satisfiable, so there is no polynomial time reduction unless P=NP.
Tim
CC BY-SA 4.0
2021-09-07T08:01:08.317Z
Your argument does not demonstrate anything like that. In particular, it is perfectly possible that the reduction has linear size even if the input formula is unsatisfiable. Your argument didn’t use anything special about 1-in-3-SAT; if it worked, it would also show that e.g. a reduction from 3-SAT to 3-SAT is impossible, which is clearly absurd.
Emil Jeřábek
CC BY-SA 4.0
2021-09-07T08:18:26.170Z
My answer shows that a globally minimal 1-in-3SAT instance is hard to find, but I believe that J.Doe is only looking for a locally minimal instance. The impossibility of a 3-SAT to 3-SAT reduction is not absurd, as it involves figuring out whether some clause is redundant.
Tim
CC BY-SA 4.0
2021-09-07T09:04:23.267Z
The question does not ask for a globally or locally minimal instance. It asks whether a reduction satisfying 1 and 2 *exists* in the first place; if it *does*, you may start worrying whether it’s possible to make it simpler. This does not answer the question at all.
Emil Jeřábek
CC BY-SA 4.0
2021-09-07T01:43:48.077Z
2021-09-07T08:23:23.767Z
2021-09-07T08:23:23.767Z
Tim
<p>The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:</p>
<p>For each 3SAT clause: <span class="math-container">$x+y+z=1$</span>
Introduce 4 new variables <span class="math-container">$\{a, b, c, d\}$</span> and replace original clause with below 3 clauses:</p>
<ol>
<li><span class="math-container">$R(x^-, a, b)=1$</span></li>
<li><span class="math-container">$R(y, b, c) =1$</span></li>
<li><span class="math-container">$R(z^-, c, d)=1$</span></li>
</ol>
<p>Query:
Given a 3SAT instance how can we reduce it into (as simple as possible) 1-in-3SAT instance with the following additional constraints:</p>
<ol>
<li>All new variables occur in at least 2 clauses.</li>
<li>There are no <em>dummy/redundant</em> clauses in the 1-in-3-SAT reduction. A dummy/redundant clause is whose addition or removal in the problem does not change the set of solutions of the problem. Thus, all clauses are <em>essential</em>.</li>
</ol>
<p>I have been stuggling with this for some time without much success.</p>

CC BY-SA 4.0
2021-09-07T08:04:12.037Z
For 1, a stronger property is achieved in https://cstheory.stackexchange.com/a/42223. For 2, something else is needed.
Emil Jeřábek
CC BY-SA 4.0
2021-09-08T07:23:39.143Z
@EmilJeřábek Thank you. It does solve the first part elegantly. For 2. is it correct to state that the new/reduced problem instance has a redundant clause if and only if the original 1 in 3 SAT instance had a redundant clause. The simple reason being that there is a 1 to 1 relation b/w solution space and the set of clauses in second problem uniquely represent the set of clauses in original 1-in-3 SAT?
J.Doe
CC BY-SA 4.0
2021-09-08T11:27:09.663Z
No. In fact, one can check that in the new instance, *each* of the new clauses is (individually) redundant.
Emil Jeřábek
CC BY-SA 4.0
2021-09-08T16:49:15.640Z
@EmilJeřábek I thought about it for a while. One of the clauses $(\neg x, \neg x', F_1)$ and $(x, x', F_1)$ are redundant so we need only one of them. But in that case we are again back to square one as $x'$ will have only 1 occurance. This doesn't seem to work (constraint 2). Can you please help me with this as I am stuck?
J.Doe
CC BY-SA 4.0
2021-09-08T17:11:18.150Z
I cannot help you with this. Condition 2 is extremely strong, and I have no idea if it’s possible to achieve it, even ignoring Condition 1.
Emil Jeřábek
<cc.complexity-theory><reductions>
3SAT to 1-in-3SAT reduction with additonal constraints
J.Doe
# 3SAT to 1-in-3SAT reduction with additonal constraints

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

The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:

For each 3SAT clause: $x+y+z=1$
Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses:

1. $R(x^-, a, b)=1$
2. $R(y, b, c) =1$
3. $R(z^-, c, d)=1$

Query:
Given a 3SAT instance how can we reduce it into (as simple as possible) 1-in-3SAT instance with the following additional constraints:

1. All new variables occur in at least 2 clauses.
2. There are no *dummy/redundant* clauses in the 1-in-3-SAT reduction. A dummy/redundant clause is whose addition or removal in the problem does not change the set of solutions of the problem. Thus, all clauses are *essential*.

I have been stuggling with this for some time without much success.

**Tags:** cc.complexity-theory, reductions

> **Comments:**
> **username_1**: For 1, a stronger property is achieved in https://cstheory.stackexchange.com/a/42223. For 2, something else is needed.  
> **username_0**: @EmilJeřábek Thank you. It does solve the first part elegantly. For 2. is it correct to state that the new/reduced problem instance has a redundant clause if and only if the original 1 in 3 SAT instance had a redundant clause. The simple reason being that there is a 1 to 1 relation b/w solution space and the set of clauses in second problem uniquely represent the set of clauses in original 1-in-3 SAT?  
> **username_1**: No. In fact, one can check that in the new instance, *each* of the new clauses is (individually) redundant.  
> **username_0**: @EmilJeřábek I thought about it for a while. One of the clauses $(\neg x, \neg x', F_1)$ and $(x, x', F_1)$ are redundant so we need only one of them. But in that case we are again back to square one as $x'$ will have only 1 occurance. This doesn't seem to work (constraint 2). Can you please help me with this as I am stuck?  
> **username_1**: I cannot help you with this. Condition 2 is extremely strong, and I have no idea if it’s possible to achieve it, even ignoring Condition 1.  

---

## 1 answers

### Answer by username_2 on 2021-09-07. Score: -2

**Edit:** This answers a related problem, in which "as simple as possible" means that the number of clauses is minimal.

Let $A$ be the given 3SAT instance. I will assume that you are looking for a corresponding 1-in-3SAT instance $B$ with as few clauses as possible, rather than some local minimum.
It also seems that you restrict yourself to instances $B$ whose variables include those of $A$, plus potentially new variables, and that any satisfying assignment for $B$ is also a satisfying assignment for $A$, and that any satisfying assignment for $A$ can be extended to a satisfying assignment for $B$ using some assignment for the new variables.

Let $c$ be the number of clauses in $B$.
If $A$ is not satisfiable, then $B$ will be an unsatisfiable 1-in-3SAT instance of constant length ($c=1$ or $c=2$ depending on whether a single clause can contain a literal and its negation).

We can in polynomial time tell whether $A$ is satisfiable based on $B$ as follows.
If $c>2$, then $A$ is satisfiable.
If $B$ has length $c$, we can find all its satisfying assignments in $O(c2^{3c})$ time, so if $c\leq 2$, we can find all satisfying assignments in constant time and hence determine whether $A$ is satisfiable.
Therefore, a reduction to a 1-in-3SAT instance with a minimum number of clauses is NP-hard.

> **Comments:**
> **username_0**: we don't know if the instance is satisfiable, has a unique solution or more than one solution. I am simply trying to find a reduction from SAT to 1-in-3-SAT but with a couple of additional constraints. I am afraid that this simply does not answer my query! we are not trying to solve the problem but a general reduction without caring about the number of solutions.  
> **username_2**: The point is that any reduction will be able to determine whether an instance is satisfiable, so there is no polynomial time reduction unless P=NP.  
> **username_1**: Your argument does not demonstrate anything like that. In particular, it is perfectly possible that the reduction has linear size even if the input formula is unsatisfiable. Your argument didn’t use anything special about 1-in-3-SAT; if it worked, it would also show that e.g. a reduction from 3-SAT to 3-SAT is impossible, which is clearly absurd.  
> **username_2**: My answer shows that a globally minimal 1-in-3SAT instance is hard to find, but I believe that username_0 is only looking for a locally minimal instance. The impossibility of a 3-SAT to 3-SAT reduction is not absurd, as it involves figuring out whether some clause is redundant.  
> **username_1**: The question does not ask for a globally or locally minimal instance. It asks whether a reduction satisfying 1 and 2 *exists* in the first place; if it *does*, you may start worrying whether it’s possible to make it simpler. This does not answer the question at all.  

---

