0
$\begingroup$

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)?

$\endgroup$
2
  • 1
    $\begingroup$ What is k? It stands for 1 or 2? If so, maybe you should just write 1 instead of k. $\endgroup$
    – domotorp
    Commented Jan 26, 2022 at 8:48
  • $\begingroup$ @domotorp k can be any fixed constant which we are free to choose as long as the main requirement is satisfied $\endgroup$
    – J.Doe
    Commented Jan 27, 2022 at 7:23

1 Answer 1

-1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.