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?