贵州大学学报（自然科学版）
貴州大學學報（自然科學版）
귀주대학학보（자연과학판）
JOURNAL OF GUIZHOU UNIVERSITY(NATURAL SCIENCE)
2005年
2期
184-192
,共9页
判定问题的复杂性%改名%极小不可满足公式%MAX+(k)-公式
判定問題的複雜性%改名%極小不可滿足公式%MAX+(k)-公式
판정문제적복잡성%개명%겁소불가만족공식%MAX+(k)-공식
complexity of decision problem%renaming%minimal unsatisfiable formulas%MAX+(k) -formulas
MAX+(k) 是极小不可满足公式的一个子类.作者引入了 MAX+(k)中公式的一种递归构造方法, 基于分裂技术并通过证明MAX(1)中公式改名问题在多项式时间内可以判定.证明了 MAX+(k)中公式的改名问题在多项式时间内可以判定.
MAX+(k) 是極小不可滿足公式的一箇子類.作者引入瞭 MAX+(k)中公式的一種遞歸構造方法, 基于分裂技術併通過證明MAX(1)中公式改名問題在多項式時間內可以判定.證明瞭 MAX+(k)中公式的改名問題在多項式時間內可以判定.
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.
