Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

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.

Abstract: 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

Keywords: 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

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013