 Premiile Ad Astra Revista Ad Astra Biblioteca de ştiinţă Cartea albă Topul universităţilor Who's who Publicaţii Teze şi dizertaţii Asociaţia Ad Astra Comunicate Ştiri Evenimente Oportunităţi de finanţare Login Înregistrare >> 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 http://xxx.lanl.gov/abs/0811.3116 Cuvinte cheie: \$epsilon\$-1-in-k SAT, overlaps, random graphs, phase transition. Adăugată pe site de Gabriel Istrate    © Ad Astra 2001-2013   