27
Views
0
CrossRef citations to date
0
Altmetric
Section A

Geometric properties of satisfying assignments of random ε-1-in-k SAT

Pages 2029-2039 | Received 19 Nov 2008, Published online: 10 Dec 2009
 

Abstract

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.

2000 AMS Subject Classifications :

ACM Classifications :

Acknowledgements

I thank Romeo Negrea for useful discussions. This work has been supported by a Marie Curie International Reintegration Grant within the 6th European Community Framework Programme, by a PN-II/‘Parteneriate’ grant from the Romanian CNCSIS and a grant from the Austrian Government.

Notes

In Citation15, the result is only stated and proved for k=3, but the method outlined there works for any k≥3.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.