Empirical Challenge for NC Theory

Ananth Hari, Uzi Vishkin

Horn-satisfiability or Horn-SAT is the problem of deciding whether a satisfying assignment exists for a Horn formula, a conjunction of clauses each with at most one positive litera…