The solution space structure of random constraint satisfaction problems with growing domains

doi:10.1088/1742-5468/2015/12/P12006

CSpace > 应用数学研究所

	The solution space structure of random constraint satisfaction problems with growing domains
	Xu, Wei 1,2; Zhang, Pan 3,4; Liu, Tian 5; Gong, Fuzhou6
	2015-12-01
发表期刊	JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
ISSN	1742-5468
页码	12
摘要	In this paper we study the solution space structure of model RB, a standard prototype of the constraint satisfaction problem (CSP), with growing domains. Using the first moment method and the second moment method, we rigorously show that in the satisfiable phase close to the satisfiability transition, solutions are clustered into an exponential number of well-separated clusters, with each cluster containing a sub-exponential number of solutions. As a consequence, the system has a clustering (dynamical) transition but no condensation transition. This picture of the phase diagram is different to other classic random CSPs that possess a fixed domain size, such as the K-satisfiability (K-SAT) problem and the graph colouring problem, where a condensation transition exists and is distinctly different to the satisfiability transition. Our result verifies some non-rigorous results obtained using the cavity method from spin glass theory.
关键词	disordered systems (theory) phase transformations (theory)
DOI	10.1088/1742-5468/2015/12/P12006
语种	英语
WOS研究方向	Mechanics ; Physics
WOS类目	Mechanics ; Physics, Mathematical
WOS记录号	WOS:000368901900006
出版者	IOP PUBLISHING LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/21854
专题	应用数学研究所
通讯作者	Liu, Tian
作者单位	1.Beihang Univ, LMIB, Beijing 100191, Peoples R China 2.Beihang Univ, Sch Math & Syst Sci, Beijing 100191, Peoples R China 3.Santa Fe Inst, Santa Fe, NM 87501 USA 4.Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China 5.Peking Univ, Sch EECS, Minist Educ, Key Lab High Confidence Software Technol, Beijing 100871, Peoples R China 6.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Xu, Wei,Zhang, Pan,Liu, Tian,et al. The solution space structure of random constraint satisfaction problems with growing domains[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2015:12.
APA	Xu, Wei,Zhang, Pan,Liu, Tian,&Gong, Fuzhou.(2015).The solution space structure of random constraint satisfaction problems with growing domains.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,12.
MLA	Xu, Wei,et al."The solution space structure of random constraint satisfaction problems with growing domains".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT (2015):12.