Exact Phase Transitions in Random Constraint Satisfaction Problems
In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur are also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.
KeXu$ Wei Li
National Laboratory of Software Development Entrironment, Department of Computer Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing, 100083, P.R. China
国际会议
International Workshop on Statistical Physics and Computer Sciences(统计物理与计算机科学交叉研究国际研讨会 )
北京
英文
215-225
2010-07-08（万方平台首次上网日期，不代表论文的发表时间）