On local equilibrium equations for clustering states

Details On local equilibrium equations for clustering states On local equilibrium equations for clustering states

2002-12-18

arxiv.org/abs/cs/0212047v2

Computer Science

Computational Complexity

9 pages

Scientific paper

In this note we show that local equilibrium equations (the generalization of the TAP equations or of the belief propagation equations) do have solutions in the colorable phase of the coloring problem. The same results extend to other optimization problems where the solutions has cost zero (e.g. K-satisfiability). On a random graph the solutions of the local equilibrium equations are associated to clusters of configurations (clustering states). On a random graph the local equilibrium equations have solutions almost everywhere in the uncolored phase; in this case we have to introduce the concept quasi-solution of the local equilibrium equations.

Affiliated with

Also associated with

No associations

Rating

On local equilibrium equations for clustering states 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 On local equilibrium equations for clustering states, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On local equilibrium equations for clustering states will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-330140