#### Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

#### Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa old.ad-astra.ro

#### Geometric Properties of Satisfying Assignments of random \$epsilon\$-1-in-k SAT

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.