Dimension-Dependent behavior in the satisfability of random k-Horn formulae
<|reference_start|>Dimension-Dependent behavior in the satisfability of random k-Horn formulae: We determine the asymptotical satisfiability probability of a random at-most-k-Horn formula, via a probabilistic analysis of a simple version, called PUR, of positive unit resolution. We show that for k=k(n)->oo the problem can be ``reduced'' to the case k(n)=n, that was solved in cs.DS/9912001. On the other hand, in the case k= a constant the behavior of PUR is modeled by a simple queuing chain, leading to a closed-form solution when k=2. Our analysis predicts an ``easy-hard-easy'' pattern in this latter case. Under a rescaled parameter, the graphs of satisfaction probability corresponding to finite values of k converge to the one for the uniform case, a ``dimension-dependent behavior'' similar to the one found experimentally by Kirkpatrick and Selman (Science'94) for k-SAT. The phenomenon is qualitatively explained by a threshold property for the number of iterations of PUR makes on random satisfiable Horn formulas.<|reference_end|>
@article{istrate2000dimension-dependent,
    title={Dimension-Dependent behavior in the satisfability of random k-Horn
  formulae},
    author={Gabriel Istrate},
    journal={arXiv preprint arXiv:cs/0007029},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0007029},
    primaryClass={cs.DS}
}