Inscriere cercetatori

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa


On the satisfiability of random k-Horn formulae

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.


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

Cuvinte cheie: random k-Horn formulae, mean-field approximation