Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions

Abstract

We study the performances of stochastic heuristic search algorithms on Uniquely Extendible Constraint Satisfaction Problems with random inputs. We show that, for any heuristic preserving the Poissonian nature of the underlying instance, the (heuristic-dependent) largest ratio ${\alpha }_a$ of constraints per variables for which a search algorithm is likely to find solutions is smaller than the critical ratio ${\alpha }_d$ above which solutions are clustered and highly correlated. In addition we show that the clustering ratio can be reached when the number k of variables per constraints goes to infinity by the so-called Generalized Unit Clause heuristic.

15 pages, 4 figures, Proceedings of the International Workshop on Statistical-Mechanical Informatics, September 16-19, 2007, Kyoto, Japan; some imprecisions in the previous version have been corrected

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• A Landscape Analysis of Constraint Satisfaction Problems
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• A variational description of the ground state structure in random satisfiability problems
• On the dynamics of the glass transition on Bethe lattices
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Dynamics of heuristic optimization algorithms on random graphs

Cited by in corpus (2)

• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Entropic barriers as a reason for hardness in both classical and quantum algorithms