Premiile Ad Astra
Revista Ad Astra
Biblioteca de știință
Cartea albă
Topul universităților
Who's who
Publicații
Teze și dizertații
Asociația Ad Astra
 
Comunicate
Știri
Evenimente
Oportunități de finanțare
 
Login
Înregistrare
 
>> English
 
   
 

Gabriel Istrate. On the satisfiability of random k-Horn formulae. In P. Winkler and J. Nesetril (eds.), " Computational Complexity and Statistical Physics" , pp. 113-136. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 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

Adăugată pe site de Gabriel Istrate

Înapoi

   
© Ad Astra 2001-2013