<p>There is a way to convert 2SAT to X3SAT that adds only one new variable per clause.</p>
<p><span class="math-container">$(a \lor b) \rightarrow (\bar a, \bar b, x)$</span></p>
<p>where <span class="math-container">$x$</span> is a new variable unique to this clause.</p>
<p>I don't know of any shorter methods for converting 3SAT other than the normal method.</p>

CC BY-SA 4.0
2023-11-19T02:36:34.353Z
2023-11-19T02:36:34.353Z
Russell Easterly
<p>Given a 3-SAT clause. Is there a way to convert 3-SAT to k-in-3-SAT such that:</p>
<p>The number of new variables introduced are less than the number of clauses (without adding dummy clauses etc.)?</p>
<p>The standard way is by introducing 4 new variables and 3 new clauses as mentioned here:
<a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Boolean_satisfiability_problem</a></p>
<p>If not is it possible for some N-SAT (N&gt;3)?</p>

CC BY-SA 4.0
2022-01-26T08:48:16.557Z
What is k? It stands for 1 or 2? If so, maybe you should just write 1 instead of k.
domotorp
CC BY-SA 4.0
2022-01-27T07:23:21.030Z
@domotorp k can be any fixed constant which we are free to choose as long as the main requirement is satisfied
J.Doe
<cc.complexity-theory><sat>
SAT to k-in-3-SAT reduction
J.Doe
# SAT to k-in-3-SAT reduction

(Asked by: username_0 on 2022-01-25)

Given a 3-SAT clause. Is there a way to convert 3-SAT to k-in-3-SAT such that:

The number of new variables introduced are less than the number of clauses (without adding dummy clauses etc.)?

The standard way is by introducing 4 new variables and 3 new clauses as mentioned here:
<https://en.wikipedia.org/wiki/Boolean_satisfiability_problem>

If not is it possible for some N-SAT (N>3)?

**Tags:** cc.complexity-theory, sat
> **Comments:**
> **username_1**: What is k? It stands for 1 or 2? If so, maybe you should just write 1 instead of k.  
> **username_0**: @domotorp k can be any fixed constant which we are free to choose as long as the main requirement is satisfied  

---

## 1 answers

### Answer by username_2 on 2023-11-19. Score: -1

There is a way to convert 2SAT to X3SAT that adds only one new variable per clause.

$(a \lor b) \rightarrow (\bar a, \bar b, x)$

where $x$ is a new variable unique to this clause.

I don't know of any shorter methods for converting 3SAT other than the normal method.


---

