Hiding Quiet Solutions in Random Constraint Satisfaction Problems

摘要：

We study constraint satisfaction problems on the socalled 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.

关键词： spin glasses and other random magnets

作者: Florent Krzakala Lenka Zdeborova

作者单位: CNRS and ESPCl ParisTech. 10 rue Vauquelin. UMR 7083 Gulliver. Paris 75000 France Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos. N

会议类型: 国际会议

会议名称: International Workshop on Statistical Physics and Computer Sciences(统计物理与计算机科学交叉研究国际研讨会 )

会议地点: 北京

会议语种:英文

页码: 74-77

在线出版日期: 2010-07-08（万方平台首次上网日期，不代表论文的发表时间）