We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g. graph coloring, many of the properties of the usual random ensemble are quantitatively identical in the planted random ensemble. We study the structural phase transitions, and the easy/hard/easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid/glass/solid phenomenology. PACS numbers: 75.50.Lk,89.70.Eg,64.70.qd Constraint satisfaction problems (CSPs) stand at the root of the theory of computational complexity [1] and arise in computer science, physics, engineering and many other fields of science. Consider a set of N discrete variables and a set of M Boolean constraints; the problem consists in finding a configuration of variables that satisfies all the constraints or in proving that no such configuration exists. Algorithmical approaches to intrinsically hard NP-complete CSPs [1] are one of the biggest challenges in today's science. Ensembles of random CSPs, where the constraints are chosen uniformly at random from some prescribed distribution, are being used to understand the average computational complexity [2, 3] . Techniques from statistical physics of glassy systems have allowed us to shed new light on the problem and on the origin of the average algorithmical hardness [4, 5, 6] . A major point in evaluating the performance of new algorithms for hard CSPs is to be able to generate difficult instances that are guaranteed to be satisfiable. Planting is the most standard way to do so: one first chooses a configuration of variables and then considers only constraints which are compatible with this planted configuration. Many planting protocols have been introduced [7, 8, 9] , however, the understanding of when and why they provide a difficult instance is still very poor compared to what is known for the purely random ensemble [4, 5, 6] . This is because planting a solution changes the properties of the ensemble. It is moreover often anticipated that the planted solution is easier to find than a random one, as has been indeed proven for high density of constraints [10, 11, 12] . Hard instances with a known solution are also appealing to cryptographic application as they provide good one-way functions. Planted instances may also result from applications where only constraints compatible with an initial state of the system are added. In this Letter we show that for a specific, yet large, class of CSPs, one can easily generate planted instances by hiding a quiet solution that does not have influence on most of the characteristics of the ensemble. The canonical example of a CSP where a solution can be planted in the quiet way is the graph q-coloring problem on which we shall illustrate our findings about the phase diagram and the average algorithmical hardness. The class of problems that allow a simple quiet hiding will be discussed towards the end of the Letter. Hiding without changing -The graph coloring problem consists in deciding if the N vertexes of a graph can be colored using only q colors in such a way that every two adjacent vertices have different colors. The control parameter is the average degree of variables c, and we consider the thermodynamical limit N → ∞. In statistical physics, this problem corresponds to a Potts antiferromagnet [13, 14] . The way to plant a quiet solution in the graph coloring problem is actually the most natural one: One assigns a random color with equal probability to each of the N vertices, and then constructs the graph by randomly throwing links between vertices of different colors. Using the cavity method [15] we describe the phase diagram and the structure of solutions in this planted ensemble. In the large N limit, the degree distribution in the planted graphs is Poissonian with mean c, and thus they are locally tree-like just as the standard random Erdös-Rényi graphs. Following the cavity approach [14, 15] the BeliefPropagation (BP) equations can be written. Denote ψ i→j s the probability that the site i takes color s in absence of the site j: where Z i→j is a normalization ensuring that  The entropy per site s = S/N can thus be computed if the distribution P (ψ) over the graph is known. Assuming the absence of long range correlations, recursive equations on this distribution can be written and solved via the population dynamics technique [15] . In the planted ensemble one needs to distinguish between the sites that were planted with different
It is only on the factorized problems where there is a very close relation between the usual random and the planted ensemble, as discussed in REF .
Hiding Quiet Solutions in Random Constraint Satisfaction Problems
Phys. Rev. Lett. 102, 238701 (2009)
Physics Computer Science Medicine