MAX+ (k)中公式改名的多项式时间可判定性(英文)  

Polynomial Decidability of Renaming for Formulas in MAX^+ (k)

作　　者：陈庆燕[1] 许道云[1] 

机构地区：[1]贵州大学计算机科学系,贵阳550025

出　　处：《贵州大学学报（自然科学版）》2005年第2期184-192,共9页Journal of Guizhou University:Natural Sciences

基　　金：国家自然科学基金(批准号: 60463001);贵州省省长专项基金

摘　　要：MAX+ (k)是极小不可满足公式的一个子类。作者引入了MAX+ (k)中公式的一种递归构造方法, 基于分裂技术并通过证明MAX(1)中公式改名问题在多项式时间内可以判定。证明了MAX+ (k)中公式的改名问题在多项式时间内可以判定。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.

关 键 词：判定问题的复杂性、改名、极小不可满足公式、MAX^+(k)-公式 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]