Premiile Ad Astra
Revista Ad Astra
Biblioteca de știință
Cartea albă
Topul universităților
Who's who
Teze și dizertații
Asociația Ad Astra
Oportunități de finanțare
>> English

Gabriel Istrate. Geometric Properties of Satisfying Assignments of random $epsilon$-1-in-k SAT. International Journal of Computer Mathematics, 86(12), pp. 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

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


Adăugată pe site de Gabriel Istrate


© Ad Astra 2001-2013