The phase transition in random Horn satisfiability and its algorithmic implications
<|reference_start|>The phase transition in random Horn satisfiability and its algorithmic implications: 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 Horn clauses in the given variables. By analyzing \PUR, a natural implementation of positive unit resolution, we show that $\lim_{n\goesto \infty} \PR ({$\Phi$ is satisfiable})= 1-F(e^{-c})$, where $F(x)=(1-x)(1-x^2)(1-x^4)(1-x^8)... $. Our method also yields as a byproduct an average-case analysis of this algorithm.<|reference_end|>
@article{istrate1999the,
    title={The phase transition in random Horn satisfiability and its algorithmic
  implications},
    author={Gabriel Istrate},
    journal={arXiv preprint arXiv:cs/9912001},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9912001},
    primaryClass={cs.DS cs.CC}
}