Filters
Results 1 - 1 of 1
Results 1 - 1 of 1.
Search took: 0.014 seconds
AbstractAbstract
[en] 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. (paper)
Primary Subject
Source
Available from http://dx.doi.org/10.1088/1742-5468/2015/12/P12006; Country of input: International Atomic Energy Agency (IAEA)
Record Type
Journal Article
Journal
Journal of Statistical Mechanics; ISSN 1742-5468;
; v. 2015(12); [12 p.]

Country of publication
Reference NumberReference Number
INIS VolumeINIS Volume
INIS IssueINIS Issue