Skip to main content
edited tags
Link
Kaveh
  • 5.5k
  • 2
  • 37
  • 52
edited tags
Link
Kaveh
  • 5.5k
  • 2
  • 37
  • 52
copy edit
Source Link
Charles Matthews
  • 12.6k
  • 35
  • 64

Horn Clauseclauses and Satisfiability.satisfiability

It is well known that Satisfiabilitysatisfiability of Horn Formulaeformulae can be checked in polynomial time using unit propagation.

But ifsuppose we relax the condition for horn clauses from at most one un-negated literals to two un-nagatednegated literals. Then is it possible to prove that satisfiability of such a formula can be checked in polynomialin time ofpolynomial in the size of the formula?

Horn Clause and Satisfiability.

It is well known that Satisfiability of Horn Formulae can be checked in polynomial time using unit propagation.

But if we relax the condition for horn clauses from at most one un-negated literals to two un-nagated literals. Then is it possible to prove that satisfiability of such a formula can be checked in polynomial time of the size of the formula?

Horn clauses and satisfiability

It is well known that satisfiability of Horn formulae can be checked in polynomial time using unit propagation.

But suppose we relax the condition for horn clauses from at most one un-negated literals to two un-negated literals. Then is it possible to prove that satisfiability of such a formula can be checked in time polynomial in the size of the formula?

Source Link
Loading