Paper Info
Title
The phase transition in random horn satisfiability and its algorithmic implications
Abstract
Let c 0 be a constant, and Φ be a random Horn formula with n variables and m = c . 2n clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn clauses in the given variables. By analyzing PUR, a natural implementation of positive unit resolution, we show that limn→∞ Pr(Φ is satisfiable) = 1 - F(e-c), where F(x) = (1 - x)(1 - x2)(1 - x4) (1 - x8) .... Our method also yields as a byproduct an average-case analysis of this algorithm.
Year
DOI
Venue
2002
10.1002/rsa.10028
Computing Research Repository
Keywords
Field
DocType
positive unit resolution,algorithmic implication,natural implementation,n variable,random horn formula,average-case analysis,nonempty horn clause,phase transition,random horn satisfiability,satisfiability
Discrete mathematics,Combinatorics,Horn clause,Phase transition,Horn-satisfiability,Mathematics
Journal
Volume
Issue
ISSN
20
4
1042-9832
ISBN
Citations 
PageRank 
0-89871-434-6
5
0.52
References 
Authors
18
1
Name
Order
Citations
PageRank
Gabriel Istrate19924.96