Loading...
Please wait, while we are loading the content...
Similar Documents
Geometric properties of satisfying assignments of random ε-1-in-kSAT
| Content Provider | Scilit |
|---|---|
| Author | Istrate, Gabriel |
| Copyright Year | 2009 |
| Description | We study the geometric structure of the set of solutions of a random ε-1-in-k SAT problem [D. Achlioptas, A. Chtcherba, G. Istrate, and C. Moore, The phase transition in 1-in-K SAT and NAE3SAT, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 721–722; A. Percus, G. Istrate, and C. Moore (eds.), Computational Complexity and Statistical Physics, Oxford University Press, Oxford, UK, 2006]. 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 identify a subregion of the satisfiable phase where the set of solutions provably forms one cluster. Next, we provide a range of parameters (c, ε) such that w.h.p. (with high probability) two assignments of a random ε-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 $ν_{ k }$∈(0, 1/(k−2)] such that w.h.p. no two satisfying assignments at distance at least $ν_{ k }$·n form a 'hole'. We believe that this is true for all $ν_{ k }$>0, and in fact solutions of a random 1-in-k SAT instance in the satisfiable phase form one cluster. |
| Related Links | http://arxiv.org/pdf/0811.3116v1.pdf |
| Ending Page | 2039 |
| Page Count | 11 |
| Starting Page | 2029 |
| ISSN | 00207160 |
| e-ISSN | 10290265 |
| DOI | 10.1080/00207160903193970 |
| Journal | International Journal of Computer Mathematics |
| Issue Number | 12 |
| Volume Number | 86 |
| Language | English |
| Publisher | Informa UK Limited |
| Publisher Date | 2009-12-01 |
| Access Restriction | Open |
| Subject Keyword | Journal: International Journal of Computer Mathematics Hardware and Architecturee Ε-1-in-k Sat Overlaps Random Graphs Phase Transition Primary 68q25 Secondary 82b27 F.2.2 G.2 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Computational Theory and Mathematics Computer Science Applications |
