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

The Structure and Complexity of MAX-MU(2)

SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年的一个热点研究方向.文章主要利用(1,*)-消解和分裂方法研究了差为2的极大极小不可满足公式集(MAX-MU(2))的结构和复杂度.

SAT Problem is a core problem in theoretical computer science. There are many ways to research into SAT Problem. Using the properties of minimal unsatisfiable formulas to study SAT Problem is a new hot way of research at present. In this paper, the structure and complexity of maxlmal minimal unsatisfiable formulas with deficiency 2 （ MAX - MU（2） ） are studied by（1, ＊） -resolution and splitting technique.