The solution space structure of random constraint satisfaction problems with growing domains
Wei Xu, Pan Zhang, Tian Liu, Fuzhou Gong · Journal of Statistical Mechanics Theory and Experiment · 2015
In this paper we study the solution space structure of model RB, a standard prototype of the constraint satisfaction problem (CSP), with growing domains. Using the first moment method and the second moment method , we rigorously show that in the satisfiable phase close to the satisfiability transition, solutions are clustered into an exponential number of well-separated clusters, with each cluster containing a sub-exponential number of solutions. As a consequence, the system has a clustering (dynamical) transition but no condensation transition. This picture of the phase diagram is different to other classic random CSPs that possess a fixed domain size, such as the K -satisfiability ( K -SAT) problem and the graph colouring problem, where a condensation transition exists and is distinctly different to the satisfiability transition. Our result verifies some non-rigorous results obtained using the cavity method from spin glass theory.