Solution Space Coupling in the Random K-Satisfiability Problem

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

	Solution Space Coupling in the Random K-Satisfiability Problem
	Zhou, HJ
刊名	COMMUNICATIONS IN THEORETICAL PHYSICS
	2013
卷号	60 期号:3 页码:363-374
关键词	CONSTRAINT SATISFACTION PROBLEMS GLASS-TRANSITION ENTROPY
ISSN号	0253-6102
通讯作者	Zeng, Y (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.
英文摘要	The random K-satisfiability (K-SAT) problem is very difficult when the clause density is close to the satisfiability threshold. In this paper we study this problem from the perspective of solution space coupling. We divide a given difficult random K-SAT formula into two easy sub-formulas and let the two corresponding solution spaces to interact with each other through a coupling field x. We investigate the statistical mechanical property of this coupled system by mean field theory and computer simulations. The coupled system has an ergodicity-breaking (clustering) transition at certain critical value x(d) of the coupling field. At this transition point, the mean overlap value between the solutions of the two solution spaces is very close to I. The mean energy density of the coupled system at its clustering transition point is less than the mean energy density of the original K-SAT problem at the temperature-induced clustering transition point. The implications of this work for designing new heuristic K-SAT solvers are discussed.
学科主题	Physics
收录类别	SCI
资助信息	Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02]; Natural National Science Foundation of China [11121403, 11225526]
语种	英语
WOS记录号	WOS:000325042500018
公开日期	2014-04-25
内容类型	期刊论文
源URL	[http://ir.itp.ac.cn/handle/311006/15278]
专题	理论物理研究所_理论物理所1978-2010年知识产出
推荐引用方式 GB/T 7714	Zhou, HJ. Solution Space Coupling in the Random K-Satisfiability Problem[J]. COMMUNICATIONS IN THEORETICAL PHYSICS,2013,60(3):363-374.
APA	Zhou, HJ.(2013).Solution Space Coupling in the Random K-Satisfiability Problem.COMMUNICATIONS IN THEORETICAL PHYSICS,60(3),363-374.
MLA	Zhou, HJ."Solution Space Coupling in the Random K-Satisfiability Problem".COMMUNICATIONS IN THEORETICAL PHYSICS 60.3(2013):363-374.