| 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年6月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 维普 万方数据 等数据库收录！ |
