<p>Given a generic K-SAT instance <span class="math-container">$S$</span> with <span class="math-container">$n$</span> boolean variables.</p>
<p>Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses introduced is more than the number of new variables introduced?</p>

CC BY-SA 4.0
2024-02-25T18:02:05.620Z
I think this answer provides such a reduction. https://cstheory.stackexchange.com/a/42223/45276
rus9384
CC BY-SA 4.0
2024-02-25T18:38:03.753Z
@rus9384 Thank you. But the $(x, x', F_1)$ and $(\neg x, \neg x', F_1)$ is essentially introducing a dummy variable $(F_1)$ that will always have to be FALSE and I am trying to avoid such tricks (dummy variables and clauses)...
TheoryQuest1
<cc.complexity-theory><reductions>
converting K-SAT clause to a p-in-L-SAT equation
TheoryQuest1
# converting K-SAT clause to a p-in-L-SAT equation

(Asked by: username_0 on 2024-02-25)

Given a generic K-SAT instance $S$ with $n$ boolean variables.

Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses introduced is more than the number of new variables introduced?

**Tags:** cc.complexity-theory, reductions
> **Comments:**
> **username_1**: I think this answer provides such a reduction. https://cstheory.stackexchange.com/a/42223/45276  
> **username_0**: @rus9384 Thank you. But the $(x, x', F_1)$ and $(\neg x, \neg x', F_1)$ is essentially introducing a dummy variable $(F_1)$ that will always have to be FALSE and I am trying to avoid such tricks (dummy variables and clauses)...  

---

## 0 answers

