Scopul nostru este sprijinirea şi promovarea cercetării ştiinţifice şi facilitarea comunicării între cercetătorii români din întreaga lume.
Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe
Autori: Gabriel Istrate
Editorial: P. Winkler and J. Nesetril, AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, "Computational Complexity and Statistical Physics", p.113-136, 2004.
Rezumat:
Kirkpatrick and Selman (Science’94) have experimentally shown that random k-satisfiability displays critical behavior , a phenomenon from Statistical Mechanics that roughly asserts that mean-field (first-order) approximations become exact in the limit of large k. I rigorously show that at-most-k-Horn 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
Cuvinte cheie: random k-Horn formulae, mean-field approximation