2002/12/07 by Giorgio Parisi, Parisi, Giorgio · 1 citation
Computer Science · Physics and Astronomy · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Cooperative Communication and Network Coding #Data Management and Algorithms #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #G.2.1 #G.3 #cond-mat.dis-nn #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0212009
13 pages, 3 figures
arxiv created 2002/12/07 · openalex publication_date 2002/12/07 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note we study the existence of a solution to the survey-propagation equations for the random K-satisfiability problem for a given instance. We conjecture that when the number of variables goes to infinity, the solution of these equations for a given instance can be approximated by the solution of the corresponding equations on an infinite tree. We conjecture (and we bring numerical evidence) that the survey-propagation equations on the infinite tree have an unique solution in the suitable range of parameters.