| MXX和MARG中公式改名的复杂性 |
| |
| 引用本文： | 许道云. MXX和MARG中公式改名的复杂性[J]. 南京大学学报(自然科学版), 2006, 23(2): 181-199 |
| |
| 作者姓名： | 许道云 |
| |
| 作者单位： | 贵州大学计算机科学系 贵阳 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China (No. 60463001,No. 10410638, No. 60310213). |
| |
| 摘 要： | 研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．
|
| 关 键 词： | 复杂性 变元改名 文字改名 极小不可满足公式 图同构 |
| 修稿时间： | 2005-06-16 |
THE COMPLEXITY OF RENAMINGS FOR FORMULAS IN MAX AND MARG |
| |
| Xu Daoyun. THE COMPLEXITY OF RENAMINGS FOR FORMULAS IN MAX AND MARG[J]. Journal of Nanjing University: Nat Sci Ed, 2006, 23(2): 181-199 |
| |
| Authors: | Xu Daoyun |
| |
| Abstract: | |
| |
| Keywords: | complexity variable renaming literal renaming minimal unsatisfiable formula graph isomorphism. |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
