您当前所在位置: 首页 > 学者

许可

  • 45浏览

  • 0点赞

  • 0收藏

  • 0分享

  • 76下载

  • 0评论

  • 引用

期刊论文

Exact Phase Transitions in Random Constraint Satisfaction Problems

许可Ke Xu Wei Li

Journal of Artifieial Intelligence Research 12(2000)93-103,-0001,():

URL:

摘要/描述

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 arc 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.

关键词:

【免责声明】以下全部内容由[许可]上传于[2010年02月05日 10时13分33秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。

我要评论

全部评论 0

本学者其他成果

    同领域成果