If a CNF contains only Horn and Xor clauses, and does not contain clauses of other types, then can its Satisfiability be determined in polynomial time?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What do you think? Have you tried applying Schaeffer's theorem to the bounded width case? $\endgroup$– Yuval FilmusCommented Nov 19, 2017 at 16:51
-
$\begingroup$ Have you tried either coming up with an algorithm or showing that the problem is NP-complete? $\endgroup$– Yuval FilmusCommented Nov 19, 2017 at 16:53
-
$\begingroup$ @Yuval Filmus - I have to admit that I am very new to this field, as a result not aware of Schaeffer's theorem. The problem that motivated my question is from a CSP that has continuous variables, whose feasibility is reducible to a SAT. I have been unsuccessful in resolving its complexity with the problem described in CSP form, but have no clue on how to go about this in SAT form. $\endgroup$– csTheoryBeginnerCommented Nov 19, 2017 at 17:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Hint: Using XOR clauses you can express "$x = \lnot y$", and this allows you to simulate general clauses by Horn clauses.
answered Nov 19, 2017 at 16:52
-
$\begingroup$ So I guess it should be NP complete. $\endgroup$ Commented Nov 19, 2017 at 17:15
-
$\begingroup$ Yes, that's the conclusion. $\endgroup$ Commented Nov 19, 2017 at 17:16