SAT问题的相变现象 |
| |
作者姓名: | 许可 李未 |
| |
作者单位: | 北京航空航天大学计算机系!北京100083 |
| |
基金项目: | 国家自然科学基金重点资助项目!(批准号:6 94330 30 ),国家教委博士点基金资助项目 |
| |
摘 要: | 相变现象是SAT问题的一个重要特性。证明了对于随机k-SAT模型,当r连续增大,到达某一个临界点时,解的结构将发生与可满足概率相当类似的突变现象,可满足赋值之间的关系突然由差别较大变得很相似。
|
关 键 词: | SAT问题 相变现象 解 临界点 主相似度 |
本文献已被 CNKI 维普 万方数据 等数据库收录! |
|