Unique—MU(2)和SYM-MU(2)的结构和复杂度

The Structure and Complexity of Unique—MU(2) and SYM-MU(2)

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

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