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.
1
-
2$\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 FilmusOct 30, 2015 at 18:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
