Loading...
Please wait, while we are loading the content...
Similar Documents
Geometric properties of satisfying assignments of random ε-1-in-k sat (2008).
| Content Provider | CiteSeerX |
|---|---|
| Author | Istrate, Gabriel |
| 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 assignments. Also, there exists ǫ0 ∈ (0, ) such that w.h.p. no two satisfying assignments at distance at least ǫ0 · n form a ”hole ” in the set of assignments. We believe that this is true for all ǫ> 0, and thus satisfying assignments of a random 1-in-k SAT instance form a single cluster. |
| File Format | |
| Publisher Date | 2008-01-01 |
| Access Restriction | Open |
| Subject Keyword | Random 1-in-k Sat Geometric Property Random 1-in-k Sat Instance Satisfying Assignment Geometric Structure Single Cluster Random 1-in-k Sat Instance Form Random 1-in-k Sat Problem |
| Content Type | Text |
