Exact phase transitions in random constraint satisfaction problems
| 文献类型 | 期刊 |
| 作者 | Xu, K[1];Li, W[2] |
| 机构 | Beijing Univ Aeronaut & Astronaut, Dept Comp Sci & Engn, Natl Lab Software Dev Environm, Beijing 100083, Peoples R China. ↓ |
| 通讯作者 | Xu, K (reprint author), Beijing Univ Aeronaut & Astronaut, Dept Comp Sci & Engn, Natl Lab Software Dev Environm, Beijing 100083, Peoples R China. |
| 来源信息 | 年:2000卷:12页码范围:93-103 |
| 期刊信息 | JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH影响因子和分区ISSN:1076-9757 |
| 摘要 | 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. |
| 收录情况 | SCIE(WOS:000087116700004) |
| 所属部门 | 计算机学院 |
| 学科 | 计算机：人工智能 |
| 被引频次 | 91 |
影响因子：1.659
JCR分区：
| 学科 | 分区 |
| COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE | Q2 |
dc:title:Exact phase transitions in random constraint satisfaction problems
dc:creator:Xu, K;Li, W
dc:date: publishDate:2000-01-01
dc:type:期刊
dc:format: Media：JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
dc:identifier: LnterrelatedLiterature：JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH.2000,12,93-103.
dc:identifier:DOI：
dc: identifier:ISBN:1076-9757
