Hiding Quiet Solutions in Random Constraint Satisfaction Problems

We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g. 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. 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.