No data available.

Please log in to see this content.

You have no subscription access to this content.

No metrics data to plot.

The attempt to load metrics for this article has failed.

The attempt to plot a graph for these metrics has failed.

The full text of this article is not currently available.

On the survey-propagation equations in random constraint satisfiability problems

### Abstract

In this paper we study the existence of a solution of the survey-propagation equations for a given instance of a random problem in the framework of constraint satisfiability. We consider the concrete examples of -satisfiability and coloring. We conjecture that when the number of variables goes to infinity, the solution of the survey-propagation equations for a given instance can be obtained by finding the (supposed unique) solution of the corresponding equations on an infinite tree. We conjecture that the survey-propagation equations on a random infinite tree have a unique solution in the suitable range of parameters. We also present analytic arguments that indicate that the survey-propagation equations do have solutions in the satisfiable phase. For simplicity of notation the argument is presented in the case of the coloring problem. The same results extend to other optimization problems where exist configurations that have cost zero, i.e., in the satisfiable phase. On a random graph the solutions of the belief-propagation equations are associated with the existence of many well separated clusters of configurations (clustering states). We argue that on a random graph the belief-propagation equations have solutions almost everywhere: the statement may be sharpened by introducing the concept of quasisolution of the belief-propagation equations.

© 2008 American Institute of Physics

Received 07 August 2008
Accepted 30 October 2008
Published online 23 December 2008

Acknowledgments:
I thank Marc Mézard and Riccardo Zecchina for useful discussions.

Article outline:

I. INTRODUCTION
II. A FAST HEURISTIC DERIVATION OF THE SURVEY EQUATIONS
A. The random -sat problem
B. The belief-propagation equations
C. The survey-propagation equations
III. THE INFINITE ROOTED TREE AND SOME CONJECTURES
A. The infinite tree
B. Some conjectures
C. A consistency check
IV. ON THE SOLUTIONS OF THE BELIEF EQUATION FOR A GIVEN GRAPH
A. Coloring a colorable graph
B. Whitening a colored graph
C. Directional whitening
V. QUASISOLUTIONS
A. On the existence of quasisolutions
B. Counting the extremal directional whitenings
VI. CONCLUSIONS

/content/aip/journal/jmp/49/12/10.1063/1.3030862

http://aip.metastore.ingenta.com/content/aip/journal/jmp/49/12/10.1063/1.3030862

Article metrics loading...

/content/aip/journal/jmp/49/12/10.1063/1.3030862

2008-12-23

2016-10-27

Full text loading...

###
Most read this month

Article

content/aip/journal/jmp

Journal

5

3

Commenting has been disabled for this content