Name
Abstract | ||
|---|---|---|
We study the structure of satisfying assignments of a random 3-Sat formula. In particular, we show that a random formula of density @a=4.453 almost surely has no non-trivial ''core'' assignments. Core assignments are certain partial assignments that can be extended to satisfying assignments, and have been studied recently in connection with the Survey Propagation heuristic for random Sat. Their existence implies the presence of clusters of solutions, and they have been shown to exist with high probability below the satisfiability threshold for k-Sat with k=9 [D. Achlioptas, F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, in: Proc. 38th ACM Symp. Theory of Computing, STOC, 2006, pp. 130-139]. Our result implies that either this does not hold for 3-Sat, or the threshold density for satisfiability in 3-Sat lies below 4.453. The main technical tool that we use is a novel simple application of the first moment method. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2008.06.053 | Theoretical Computer Science |
Keywords | DocType | Volume |
threshold density,first-moment method,core assignment,random sat,random formula,3-sat lie,random constraint satisfaction problem,phase transitions,3-sat formula,acm symp,satisfiability threshold,satisfying assignment,random 3-sat,survey propagation,threshold of satisfiability,computational complexity,satisfiability | Journal | 407 |
Issue | ISSN | Citations |
1-3 | Theoretical Computer Science | 13 |
PageRank | References | Authors |
0.70 | 15 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elitza Maneva | 1 | 390 | 24.97 |
| Alistair Sinclair | 2 | 1506 | 308.40 |