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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 15, 2017 at 17:19
  • $\begingroup$ @csTheoryBeginner You should post this as a separate question. $\endgroup$
    – Kyle Jones
    Commented Nov 17, 2017 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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