Computer Science – Computational Complexity
Scientific paper
2007-09-04
Journal of Physics: Conference Series 95 (2008) 012013
Computer Science
Computational Complexity
15 pages, 4 figures, Proceedings of the International Workshop on Statistical-Mechanical Informatics, September 16-19, 2007, K
Scientific paper
10.1088/1742-6596/95/1/012013
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.
Altarelli Fabrizio
Monasson Remi
Zamponi Francesco
No associations
LandOfFree
Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-414305