SODA

Clustering of solutions in hard satisfiability problems

Ardelius, John and Aurell, Erik and Krishnamurthy, Supriya (2007) Clustering of solutions in hard satisfiability problems. Journal of Statistical Mechanics: Theory and Experiment (P10012). ISSN 1742-5468 (Online)

Full text not available from this repository.

Official URL: http://www.iop.org/EJ/abstract/1742-5468/2007/10/P...

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.

Item Type:Article
Uncontrolled Keywords:finite-size scaling; energy landscapes (experiment); network dynamics; random graphs, networks
ID Code:2777
Deposited By:Vicki Carleson
Deposited On:18 Mar 2008
Last Modified:18 Nov 2009 16:14

Repository Staff Only: item control page