Abstract
We study the geometric structure of the set of solutions of random -1-in-k SAT problem. For , two satisfying assignments and are -connected if there exists a sequence of satisfying assignments connecting them by changing at most bits at a time. We first prove that w.h.p. two assignments of a random -1-in- SAT instance are -connected, conditional on being satisfying assignments. Also, there exists such that w.h.p. no two satisfying assignments at distance at least form a "hole" in the set of assignments. We believe that this is true for all , and thus satisfying assignments of a random 1-in- SAT instance form a single cluster.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.