Autori: Gabriel Istrate

Editorial: International Journal of Computer Mathematics, 86(12), p.2029-2039, 2009.

Rezumat:

We study the geometric structure of the set of solutions of random $epsilon$-1-in-k 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$-1-in-$k$ SAT instance with $n$ variables and $cn$ clauses are $O(log n)$-connected, conditional on being satisfying assignments. Also, for random instances of 1-in-$k$ SAT in the satisfiable phase we show that there exists $nu_{k}in (0,frac{1}{k-2}]$ 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 1-in-$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

Cuvinte cheie: $epsilon$-1-in-k SAT, overlaps, random graphs, phase transition.

URL: http://dx.doi.org/10.1080/00207160903193970