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$
5
  • $\begingroup$ anyone please?? $\endgroup$
    – J.Doe
    Jan 26, 2022 at 8:27
  • 1
    $\begingroup$ What is k? It stands for 1 or 2? If so, maybe you should just write 1 instead of k. $\endgroup$
    – domotorp
    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
    Jan 27, 2022 at 7:23
  • $\begingroup$ @domotorp any insights please? $\endgroup$
    – J.Doe
    Jan 28, 2022 at 7:56
  • $\begingroup$ I'm sorry but the problem doesn't interest me that much. $\endgroup$
    – domotorp
    Jan 28, 2022 at 9:05

1 Answer 1

0
$\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 that you have read and understand our privacy policy and code of conduct.

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