ﻻ يوجد ملخص باللغة العربية
We investigate the clustering transition undergone by an exemplary random constraint satisfaction problem, the bicoloring of $k$-uniform random hypergraphs, when its solutions are weighted non-uniformly, with a soft interaction between variables belonging to distinct hyperedges. We show that the threshold $alpha_{rm d}(k)$ for the transition can be further increased with respect to a restricted interaction within the hyperedges, and perform an asymptotic expansion of $alpha_{rm d}(k)$ in the large $k$ limit. We find that $alpha_{rm d}(k) = frac{2^{k-1}}{k}(ln k + ln ln k + gamma_{rm d} + o(1))$, where the constant $gamma_{rm d}$ is strictly larger than for the uniform measure over solutions.
The typical complexity of Constraint Satisfaction Problems (CSPs) can be investigated by means of random ensembles of instances. The latter exhibit many threshold phenomena besides their satisfiability phase transition, in particular a clustering or
Random Constraint Satisfaction Problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information the
Random constraint satisfaction problems undergo several phase transitions as the ratio between the number of constraints and the number of variables is varied. When this ratio exceeds the satisfiability threshold no more solutions exist; the satisfia
We study the phase diagram and the algorithmic hardness of the random `locked constraint satisfaction problems, and compare them to the commonly studied non-locked problems like satisfiability of boolean formulas or graph coloring. The special proper
The performance of a D-Wave Vesuvius quantum annealer was recently compared to a suite of classical algorithms on a class of constraint satisfaction instances based on frustrated loops. However, the construction of these instances leads the maximum c