Clustering of solutions in hard satisfiability problems
arXiv:cond-mat/0702672 · doi:10.1088/1742-5468/2007/10/P10012
Abstract
We study the structure of the solution space and behavior of local search methods on random 3-SAT problems close to the SAT/UNSAT transition. Using the overlap measure of similarity between different solutions found on the same problem instance we show that the solution space is shrinking as a function of alpha. We consider chains of satisfiability problems, where clauses are added sequentially. In each such chain, the overlap distribution is first smooth, and then develops a tiered structure, indicating that the solutions are found in well separated clusters. On chains of not too large instances, all solutions are eventually observed to be in only one small cluster before vanishing. This condensation transition point is estimated to be alpha_c = 4.26. The transition approximately obeys finite-size scaling with an apparent critical exponent of about 1.7. We compare the solutions found by a local heuristic, ASAT, and the Survey Propagation algorithm up to alpha_c.
8 pages, 9 figures
References in corpus (12)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Clustering of solutions in the random satisfiability problem
- Survey Propagation as local equilibrium equations
- A variational description of the ground state structure in random satisfiability problems
- Focused Local Search for Random 3-Satisfiability
- Landscape of solutions in constraint satisfaction problems
- Behavior of heuristics and state space structure near SAT/UNSAT transition
- Relaxation and Metastability in the RandomWalkSAT search procedure
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- A backtracking survey propagation algorithm for K-satisfiability
- Comparing Beliefs, Surveys and Random Walks