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.

Log in via your institution

Log in to Taylor & Francis Online

PDF download + Online access

  • 48 hours access to article PDF & online version
  • Article PDF can be downloaded
  • Article PDF can be printed
USD 61.00 Add to cart

Issue Purchase

  • 30 days online access to complete issue
  • Article PDFs can be downloaded
  • Article PDFs can be printed
USD 1,129.00 Add to cart

* Local tax will be added as applicable

Related Research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.