The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:

For each 3SAT clause: $x+y+z=1$ Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses:

  1. $R(x^-, a, b)=1$
  2. $R(y, b, c) =1$
  3. $R(z^-, c, d)=1$

In a similar vein is what is the generic way to convert N-SAT to 1-in-3-SAT such that:

  1. The number of new variables introduced are minimum possible?
  2. The number of clauses are maximum possible?

We can always reduce N-SAT to a set of 3-SAT clauses and then convert each of those as described above but is it the most optimal way (that satisfies the above two conditions) or is it possible to do better?

  • $\begingroup$ I would guess that optimal conversions are at least NP-intermediate. For example, in some formulas you could apply the distributive law backwards, which could result in fewer dummy variables needed than you'd get from the plain reduction from k-SAT to 3-SAT. And applying the distributive law backwards seems hard. $\endgroup$
    – rus9384
    Commented Feb 14 at 11:42
  • $\begingroup$ @rus9384 Thanks. Is there a reference or a link for this that I can check? And a follow up Question: Can we do anything better than the standard procedure mentioned above? $\endgroup$ Commented Feb 15 at 7:02
  • $\begingroup$ Not sure about the reference, but, suppose you have a formula like $(x_1\lor x_2\lor y_1\lor y_2)\land(x_1\lor x_2\lor y_3\lor y_4)\land(x_3\lor x_4\lor y_1\lor y_2)\land(x_3\lor x_4\lor y_3\lor y_4)$. Then, you can reduce it to 3-SAT as $(z_1\lor x_1\lor x_2)\land(\overline{z_1}\lor x_3\lor x_4)\land(z_2\lor y_1\lor y_2)\land(\overline{z_2}\lor y_3\lor y_4)$. Whereas the standard reduction would add 4 variables. $\endgroup$
    – rus9384
    Commented Feb 15 at 8:20


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.