| MAX+(k)中公式改名的多项式时间可判定性 |
| |
| 引用本文： | 陈庆燕,许道云.MAX+(k)中公式改名的多项式时间可判定性[J].贵州大学学报(自然科学版),2005,22(2):184-192. |
| |
| 作者姓名： | 陈庆燕 许道云 |
| |
| 作者单位： | 贵州大学计算机科学系,贵阳,550025;贵州大学计算机科学系,贵阳,550025 |
| |
| 基金项目： | 国家自然科学基金(批准号:60463001),贵州省省长专项基金 |
| |
| 摘 要： | MAX^ (k)是极小不可满足公式的一个子类。作者引入了MAX^ (k)中公式的一种递归构造方法，基于分裂技术并通过证明MAX(1)中公式改名问题在多项式时间内可以判定。证明了MAX^ (k)中公式的改名问题在多项式时间内可以判定。
|
| 关 键 词： | 判定问题的复杂性 改名 极小不可满足公式 MAX+(k)-公式 |
| 文章编号： | 1000-5269(2005)02-0184-09 |
| 修稿时间： | 2005年2月2日 |
Polynomial Decidability of Renaming for Formulas in MAX+ (k) |
| |
| CHEN Qing-yan,XU Dao-yun.Polynomial Decidability of Renaming for Formulas in MAX+ (k)[J].Journal of Guizhou University(Natural Science),2005,22(2):184-192. |
| |
| Authors: | CHEN Qing-yan XU Dao-yun |
| |
| Abstract: | MAX +(k) is a subclass of minimal unsatisfiable formulas. A method is introduced to show that the formulas in MAX +(k) can be constructed recursively. Based on the splitting technology and the fact that the complexities of renaming of formulas in MAX(1) are polynomial, we prove that the renaming problems for formulas in MAX +(k) can be decided in polynomial time. |
| |
| Keywords: | complexity of decision problem renaming minimal unsatisfiable formulas MAX +(k) -formulas |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
