Sharp Thresholds for a Random Constraint Satisfaction Problem

• 作者: Ya'nan Liu
• 来源期刊: 应用科学(英文)
• 学科: 数学
• 关键词: d-p-RB Model Phase Transition DOMAIN Size CONSTRAINT TIGHTNESS Second MOMENT Method
• 年，卷（期）: 2017,（10）
• 页码范围: 574-584
• 页数: 11页
• 分类号: O1

摘要

The phenomenon of phase transition in constraint satisfaction problems (CSPs) plays a crucial role in the field of artificial intelligence and computational complexity theory. In this paper, we propose a new random CSP called d-p-RB model, which is a generalization of RB model on domain size d and constraint tightness p. In this model, the variable domain size d?Ε [ nα, nny], and all constraints are uniformly divided into several groups with different constraint tightness p. It is proved by the second moment method that the d-p-RB model undergoes phase transition from a region where almost all instances are satisfiable to a region where almost all instances are unsatisfiable as the control parameter increases. Moreover, the threshold value at which the phase transition occurs is located exactly.