Solution space structure of random constraint satisfaction problems with growing domains

摘要: In this paper we study the solution space structure of model RB, a standard prototype Constraint Satisfaction Problem (CSPs) with growing domains. Using rigorous first and second moment method, show that in solvable phase close to satisfiability transition, solutions are clustered into exponential number well-separated clusters, each cluster contains sub-exponential solutions. As consequence, system has clustering (dynamical) transition but no condensation transition. This picture diagram is different from other classic random CSPs fixed domain size, such as K-Satisfiability (K-SAT) graph coloring problems, where exists distinct Our result verifies non-rigorous results obtained using cavity method spin glass theory, sheds light on structures spaces problems large states.