2
$\begingroup$

If a CNF contains both horn and dual horn clauses and does not contain clauses of other types, then can its Satisfiability always be determined in polynomial time?

If the answer to the above problem is yes, then suppose we only add XOR clauses in addition to horn and dual horn clauses, can the Satisfiability of this type of CNF be determined in polynomial time?

$\endgroup$
2
$\begingroup$

3-CNF formulas contain a mixture of only Horn and dual-Horn clauses. 3-SAT, the Boolean satisfiability problem over 3-CNF formulas, is known to be NP-complete. So it is unlikely that the satisfiability of such formulas can be decided in polynomial time.

$\endgroup$
  • $\begingroup$ Thank you @Kyle Jones. If I may ask, what if the CNF contains only Horn and Xor clauses, then what is the complexity of determining Satisfiability? $\endgroup$ – csTheoryBeginner Nov 15 '17 at 17:19
  • $\begingroup$ @csTheoryBeginner You should post this as a separate question. $\endgroup$ – Kyle Jones Nov 17 '17 at 17:54

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.