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

• 作者: 许道云 陈庆燕
• 来源期刊: 贵州大学学报（自然科学版）
• 学科: 工学
• 关键词: 判定问题的复杂性 改名 极小不可满足公式 MAX+(k)-公式
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 专题研究
• 页码范围: 184-192
• 页数: 9页
• 分类号: TP301.6
• 字数: 3410字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5269.2005.02.017

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	陈庆燕	贵州大学计算机科学系	1	2	1.0	1.0