Dimension-Dependent behavior in the satisfability of random k-Horn formulae

Details Dimension-Dependent behavior in the satisfability of random k-Horn formulae Dimension-Dependent behavior in the satisfability of random k-Horn formulae

2000-07-18

arxiv.org/abs/cs/0007029v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dimension-Dependent behavior in the satisfability of random k-Horn formulae does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dimension-Dependent behavior in the satisfability of random k-Horn formulae, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dimension-Dependent behavior in the satisfability of random k-Horn formulae will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-631057