| 正则3-SAT问题的相变现象 |
| |
| 引用本文： | 张明明,许道云.正则3-SAT问题的相变现象[J].计算机科学,2016,43(4):33-36. |
| |
| 作者姓名： | 张明明 许道云 |
| |
| 作者单位： | 贵州大学计算机科学与技术学院 贵阳550025,贵州大学计算机科学与技术学院 贵阳550025 |
| |
| 基金项目： | 本文受国家自然科学基金(61262006)资助 |
| |
| 摘 要： | 通过对3-CNF公式加以限制,要求其中每个变元出现的次数相同,引出正则3-SAT问题。进一步,通过对两种子句产生机制形成的(3,s)-CNF公式进行可满足性观察,发现在规模较小的情况下,正则3-CNF公式比非正则3-CNF公式更容易满足。从而推测与非正则3-SAT问题相比,正则3-SAT问题的相变点有偏移现象。最后,从变元自由度的角度对这一现象给出了定性解释。
|
| 关 键 词： | 正则CNF公式 SAT问题 相变 变元自由度 |
| 收稿时间： | 2015/5/17 0:00:00 |
| 修稿时间： | 2015/8/10 0:00:00 |
Phase Transition Phenomenon of Regular 3-SAT Problem |
| |
| ZHANG Ming-ming and XU Dao-yun.Phase Transition Phenomenon of Regular 3-SAT Problem[J].Computer Science,2016,43(4):33-36. |
| |
| Authors: | ZHANG Ming-ming and XU Dao-yun |
| |
| Affiliation: | College of Computer Science and Technology,Guizhou University,Guiyang 550025,China and College of Computer Science and Technology,Guizhou University,Guiyang 550025,China |
| |
| Abstract: | |
| |
| Keywords: | |
|
|
点击此处可从《计算机科学》下载全文 |
|
