| Some Hard Examples for the Resolution Method |
| |
| 引用本文： | Yu Xiangdong. Some Hard Examples for the Resolution Method[J]. 计算机科学技术学报, 1990, 5(3): 302-304. DOI: 10.1007/BF02945319 |
| |
| 作者姓名： | Yu Xiangdong |
| |
| 作者单位： | Huazhong University |
| |
| 基金项目： | now in Department of Computer Science,Columbia University in the City of New York. |
| |
| 摘 要： | Given n propositional variables,let Kn(i,j),0≤i≤j≤n,be the set(or disjunction)of all conjunctions of i literals of which exactly j literals are negative.Dunham and Wang conjectured that it may require exponential time to decide that every disjunction Kn(i,j)is not valid by the resolution metho.This paper gives a proof of the conjecture and then exhibits a new counterexample to the feasibility of the resolution or consensus method.
|
| 关 键 词： | MP问题 可行性算法 分解方法 |
Some hard examples for the resolution method |
| |
| Xiangdong Yu. Some hard examples for the resolution method[J]. Journal of Computer Science and Technology, 1990, 5(3): 302-304. DOI: 10.1007/BF02945319 |
| |
| Authors: | Xiangdong Yu |
| |
| Affiliation: | Huazhong University of Science and Technology Wuhan; |
| |
| Abstract: | Givenn propositional variables, letK n (i, j), 0≤i≤j≤n, be the set (or disjunction) of all conjunctions ofi literals of which exactlyj literals are negative. Dunham and Wang conjectured that it may require exponential time to decide that every disjunctionK n (i, j) is not valid by the resolution method. This paper gives a proof of the conjecture and then exhibits a new counterexample to the feasibility of the resolution or consensus method. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |
