Published in

American Physical Society, Physical Review Letters, 23(102), 2009

DOI: 10.1103/physrevlett.102.238701

Links

Tools

Export citation

Search in Google Scholar

Hiding Quiet Solutions in Random Constraint Satisfaction Problems

Journal article published in 2009 by Florent Los Alamos National Laboratory Krzakala ORCID, Lenka Los Alamos National Laboratory Zdeborová
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Green circle
Published version: archiving allowed
Upload
Policy details
Data provided by SHERPA/RoMEO

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. ; Comment: 4 pages, 3 figures