| MARG-MU(2)的结构和复杂度 |
| |
| 引用本文： | 徐小萍.MARG-MU(2)的结构和复杂度[J].井冈山学院学报,2009,30(2). |
| |
| 作者姓名： | 徐小萍 |
| |
| 作者单位： | 襄樊学院,数学与计算机学院,湖北,襄樊,441053 |
| |
| 摘 要： | SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向.本文主要利用(1,*)-消解方法研究了差为2的边缘极小不可满足公式集(MARG-MU(2))的结构和复杂度:在结构方面,MARG-MU(2)中的公式要么是F22,要么是某一文字在其中仅出现一次的公式;在复杂度方面,如果MARG-MU(2)对(1,*)-消解封闭,则某个含有n个变元和n+2个子句的公式是否为MARG-MU(2)中的公式的问题可以在时间0(n3)内被判定.
|
| 关 键 词： | 极小不可满足公式 可满足性问题 边缘 消解 |
The structure and complexity of MARG-MU(2) |
| |
| XU Xiao-ping.The structure and complexity of MARG-MU(2)[J].Journal of Jinggangshan University,2009,30(2). |
| |
| Authors: | XU Xiao-ping |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
