Hiding Quiet Solutions in Random Constraint Satisfaction Problems

Abstract

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.

4 pages, 3 figures

References in corpus (5)

• On the freezing of variables in random constraint satisfaction problems
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Potts Glass on Random Graphs
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy