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?

  • $\begingroup$ I think this answer provides such a reduction. cstheory.stackexchange.com/a/42223/45276 $\endgroup$
    – rus9384
    Commented Feb 25 at 18:02
  • $\begingroup$ @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)... $\endgroup$ Commented Feb 25 at 18:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.