2002/12/18 by Giorgio Parisi, Parisi, Giorgio · 2 citations
Computer Science · Medicine · Physics and Astronomy · #Cellular Automata and Applications #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Physical sciences #G.2.1 #G.3 #Mathematical and Theoretical Epidemiology and Ecology Models #cond-mat.dis-nn #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0212047
9 pages
openalex publication_date 2002/12/18 · arxiv created 2005/03/13 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.