The phase transition in random Horn satisfiability and its algorithmic implications

Gabriel Istrate

Let c>0 be a constant, and $\Phi$ be a random Horn formula with n variables and $m=c\cdot 2^n$ clauses, chosen uniformly at random (with repetition) from the set of all nonempty Hor…