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 old.ad-astra.ro

Facebook

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.

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

URL: http://www.amazon.com/gp/product/0821835513/sr=8-5/qid=1139805173/ref=sr_1_5/103-7873921-2045459?%5Fencoding=UTF8