On the satisfability of random k-Horn formulae

Abstract

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)\to \infty$ 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.

the latest version simply updates the title of the paper to conform to the published version

References in corpus (4)

• The Scaling Window of the 2-SAT Transition
• Non-Mean-Field Behavior of Realistic Spin Glasses
• Recent rigorous results support the predictions of spontaneously broken replica symmetry for realistic spin glasses
• Response to Parisi's Comment on ``Non-mean-field behavior of realistic spin glasses''