Gabriel Istrate. On the satisfiability of random kHorn formulae. In P. Winkler and J. Nesetril (eds.), " Computational Complexity and Statistical Physics" , pp. 113136. AMSDIMACS Series in Discrete Mathematics and Theoretical Computer Science, 2004.
Abstract:
Kirkpatrick and Selman (Science'94) have experimentally shown that random ksatisfiability displays critical behavior , a phenomenon from Statistical Mechanics that roughly asserts that meanfield (firstorder) approximations become exact in the limit of large k. I rigorously show that atmostkHorn satisfiability displays critical behavior, and explain it by a threshold property of positive unit resolution.
A preliminary version can be read from
http://xxx.lanl.gov/abs/cs.DS/0007029
Keywords:
random kHorn formulae, meanfield approximation
URL:
http://www.amazon.com/gp/product/0821835513/sr=85/qid=1139805173/ref=sr_1_5/10378739212045459?%5Fencoding=UTF8
Posted by
Gabriel Istrate
Back
