MU(1)内公式改名的多项式可判定性

• 作者: 许道云
• 来源期刊: 贵州大学学报(自然科学版)
• 学科: 工学
• 关键词: 复杂性 改名 极小不可满足公式
• 年，卷（期）: 2003,（1）
• 所属期刊栏目: 专题研究
• 页码范围: 9-19,35
• 页数: 12页
• 分类号: O141.3|TP301.5
• 字数: 5519字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5269.2003.01.002

摘要

研究判定合取范式公式F和H之间是否存在一个改名ψ使得ψ(F)=H的计算复杂性.公式的改名是将命题变元映到变元本身或变元的否定的一个映射,对于极小不可满足公式的子类MU(1)中的公式,我们证明了其改名判定问题在多项式时间内是可判定的.

作者信息

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