2
$\begingroup$

Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would be very unlikely in that it would imply P = NP? I ask because I know that there are some types of problems involving 3-literal-clauses which can be transformed into equivalent 2-sat/Hornsat clauses. I'm thinking specifically of 2-or-3 SAT which can be solved by 2-sat/anti-Hornsat clauses or 1-or-3 SAT which can be solved using affine clauses.

$\endgroup$
  • 1
    $\begingroup$ You don't need Schaefer's theorem at all here since we already know 3SAT is NP-complete whereas 2SAT and the other examples are in P. $\endgroup$ – Yuval Filmus Oct 30 '15 at 18:09
3
$\begingroup$

Schaefer's dichotomy theorem doesn't purport to claim anything about what transformations might be possible / not possible.

However, as Yuval says, we don't need Schaefer's theorem. We already know that 3SAT is NP-complete. Therefore, we know that if there is a polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance, then P = NP. Put another way, if P $\ne$ NP (as many researchers suspect to be the case), then there is no polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance. Put yet another way, finding such a transformation that provably works is at least as hard as proving that P = NP.

The same holds for a transformation to any other set of formulas that are known to have a polynomial-time algorithm for testing satisfiable (e.g., the conjunction of Horn clauses).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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