| 关于SAT问题物理模型猜想的一个反例 |
| |
| 引用本文： | 赵孝武,黄文奇. 关于SAT问题物理模型猜想的一个反例[J]. 华中科技大学学报(自然科学版), 2000, 28(11): 25-27 |
| |
| 作者姓名： | 赵孝武 黄文奇 |
| |
| 作者单位： | 华中理工大学计算机科学与工程学院 |
| |
| 基金项目： | 国家重点基础研究发展规划(G1998030600);国家高技术研究发展863计划;中国科学院软件研究所计算机科学实验室开放课题基金资助项目. |
| |
| 摘 要： | 针对关于SAT问题物理模型的一个猜想,得到了该猜想成立的必要条件.然后构造出反例,说明该猜想是不成立的.同时指出,考虑到"算法吸引区"的存在,这并不降低应用该物理模型求解SAT问题的良好的现实效果.
|
| 关 键 词： | 合取范式 可满足性 势能函数 |
| 文章编号： | 1000-8616(2000)11-0025-03 |
| 修稿时间： | 2000-05-21 |
A Counterexample of a Physical Model Hypothesis for SAT Problem |
| |
| Abstract: | Considering the hypothesis based on a physical mode for SAT problem, a necessary condition for the hypothesis is obtained. A counterexample is constructed to show that the hypothesis is not true. This counterexample does not damage the good practical effect by applying this physical model to solve SAT problem when the existence of algorithmic absorption region. |
| |
| Keywords: | CNF satisfiability potential funct| |
| 本文献已被 万方数据 等数据库收录！ |
