Gabriel Istrate. Geometric Properties of Satisfying Assignments of random $epsilon$1ink SAT. International Journal of Computer Mathematics, 86(12), pp. 20292039, 2009.
Abstract:
We study the geometric structure of the set of solutions of random $epsilon$1ink SAT problem. For $l geq 1$, two satisfying assignments $A$ and $B$ are $l$connected if there exists a sequence of satisfying assignments connecting them by changing at most $l$ bits at a time.
We first identify a subregion of the satisfiable phase where the set of solutions provably forms one cluster. Next we provide a range of parameters $(c,epsilon)$ such that w.h.p. two assignments of a random $epsilon$1in$k$ SAT instance with $n$ variables and $cn$ clauses are $O(log n)$connected, conditional on being satisfying assignments. Also, for random instances of 1in$k$ SAT in the satisfiable phase we show that there exists $nu_{k}in (0,frac{1}{k2}]$ such that w.h.p. no two satisfying assignments at distance at least $nu_{k}cdot n$ form a "hole". We believe that this is true for all $nu_{k}>0$, and in fact solutions of a random 1in$k$ SAT instance in the satisfiable phase form one cluster.
A preliminary version of this paper can be freely downloaded from
http://xxx.lanl.gov/abs/0811.3116
Keywords:
$epsilon$1ink SAT, overlaps, random graphs, phase transition.
URL:
http://dx.doi.org/10.1080/00207160903193970
Posted by
Gabriel Istrate
Back
