Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- 8 June 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 102 (23) , 238701
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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropyPhysical Review E, 2009
- Constraint satisfaction problems with isolated solutions are hardJournal of Statistical Mechanics: Theory and Experiment, 2008
- Locked Constraint Satisfaction ProblemsPhysical Review Letters, 2008
- Potts glass on random graphsEurophysics Letters, 2008
- Phase transitions in the coloring of random graphsPhysical Review E, 2007
- Gibbs states and the set of solutions of random constraint satisfaction problemsProceedings of the National Academy of Sciences, 2007
- Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratiosJournal of Physics A: Mathematical and Theoretical, 2007
- Coloring Random GraphsPhysical Review Letters, 2002
- Random-satisfiability problem: From an analytic solution to an efficient algorithmPhysical Review E, 2002
- Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics ApproachPhysical Review Letters, 2002