MARG-MU(2)的结构和复杂度

• 作者: 徐小萍
• 来源期刊: 井冈山学院学报(自然科学版)
• 学科: 工学
• 关键词: 极小不可满足公式 可满足性问题 边缘 消解
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 数学与物理
• 页码范围: 30-33
• 页数: 4页
• 分类号: TP301.5
• 字数: 3778字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-8085.2009.02.010

摘要

SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向.本文主要利用(1,*)-消解方法研究了差为2的边缘极小不可满足公式集(MARG-MU(2))的结构和复杂度:在结构方面,MARG-MU(2)中的公式要么是F22,要么是某一文字在其中仅出现一次的公式;在复杂度方面,如果MARG-MU(2)对(1,*)-消解封闭,则某个含有n个变元和n+2个子句的公式是否为MARG-MU(2)中的公式的问题可以在时间0(n3)内被判定.