| Hiding quiet solutions in random constraint satisfaction problems. | |
| | |
MedLine Citation:
|
PMID: 19658978 Owner: NLM Status: PubMed-not-MEDLINE |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
Florent Krzakala; Lenka Zdeborová |
Related Documents
:
|
14525248 - Tokamak equilibria with reversed current density. 17332018 - Rh_tsp_map 3.0: end-to-end radiation hybrid mapping with improved speed and quality con... 17512558 - On some optimization problems in molecular biology. 2064288 - The diagnosis of acute abdominal pain with computer assistance: worldwide perspective. 8688118 - A comparison of finite element codes for the solution of biphasic poroelastic problems. 16818318 - Response to the distilled spirits industry council of australia inc. position paper 'al... |
Publication Detail:
|
Type: Journal Article Date: 2009-06-08 |
Journal Detail:
|
Title: Physical review letters Volume: 102 ISSN: 0031-9007 ISO Abbreviation: Phys. Rev. Lett. Publication Date: 2009 Jun |
Date Detail:
|
Created Date: 2009-08-07 Completed Date: 2009-08-25 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 0401141 Medline TA: Phys Rev Lett Country: United States |
Other Details:
|
Languages: eng Pagination: 238701 Citation Subset: - |
Affiliation:
|
CNRS and ESPCI ParisTech, UMR 7083 Gulliver, Paris, France. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Effective medium theory for reaction rates and diffusion coefficients of heterogeneous systems.
Next Document: Asymptotic behavior of the kleinberg model.