CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS

CORC > 理论物理研究所 > 中国科学院理论物理研究所 > 理论物理所科研产出 > 理论物理所1978-2010年知识产出

	CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS
	Zhou, Haijun; Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
刊名	INTERNATIONAL JOURNAL OF MODERN PHYSICS B
	2010
卷号	24 期号:18 页码:3479-3487
关键词	Glass-transition Cavity Method Dynamics
ISSN号	0217-9792
英文摘要	Random constraint satisfaction problems are interesting model systems for spin-glasses and glassy dynamics studies. As the constraint density of such a system reaches certain threshold value, its solution space may split into extremely many clusters. In this work we argue that this ergodicity-breaking transition is preceded by a homogeneity-breaking transition. For random K-SAT and K-XORSAT, we show that many solution communities start to form in the solution space as the constraint density reaches a critical value alpha(cm), with each community containing a set of solutions that are more similar with each other than with the outsider solutions. At alpha(cm) the solution space is in a critical state. The connection of these results to the onset of dynamical heterogeneity in lattice glass models is discussed.
学科主题	Physics
URL标识	查看原文
WOS记录号	WOS:000281264700002
公开日期	2012-08-02
内容类型	期刊论文
源URL	[http://ir.itp.ac.cn/handle/311006/5075]
专题	理论物理研究所_理论物理所1978-2010年知识产出
通讯作者	Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Zhou, Haijun,Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China. CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS[J]. INTERNATIONAL JOURNAL OF MODERN PHYSICS B,2010,24(18):3479-3487.
APA	Zhou, Haijun,&Zhou, HJ , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China.(2010).CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS.INTERNATIONAL JOURNAL OF MODERN PHYSICS B,24(18),3479-3487.
MLA	Zhou, Haijun,et al."CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS".INTERNATIONAL JOURNAL OF MODERN PHYSICS B 24.18(2010):3479-3487.