Name
Abstract | ||
|---|---|---|
We study the geometric structure of the set of solutions of random ǫ-1-in-k SAT problem (2, 15). For l � 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 prove that w.h.p. two assignments of a random ǫ-1-in-k SAT instance are O(log n)-connected, conditional on being satisfying assign- ments. Also, there exists ǫ0 2 (0, 1 |
Year | Venue | Keywords |
|---|---|---|
2008 | International Journal of Computer Mathematics | overlaps,phase transition. ams categories: primary 68q25,random graphs,secondary 82b27.,ǫ-1-in-k sat,satisfiability |
Field | DocType | Volume |
Discrete mathematics,Binary logarithm,#SAT,Combinatorics,Mathematical optimization,Random graph,Existential quantification,Mathematical analysis,Sat problem,Mathematics,Computational complexity theory | Journal | abs/0811.3 |
ISSN | Citations | PageRank |
International Journal of Computer Mathematics, 86(12), pp.
2029-2039, 2009 | 0 | 0.34 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gabriel Istrate | 1 | 99 | 24.96 |
| vasile parvan | 2 | 0 | 0.34 |