d-正则(k,s)-SAT问题的NP完全性  

NP-completeness of d-regular(k,s)-SAT Problem

作　　者：符祖峰[1,2] 许道云 FU Zu-Feng;XU Dao-Yun(College of Computer Science and Technology,Guizhou University,Guiyang 550025,China;School of Electronic and Information Engineering,Anshun University,Anshun 561000,China)

机构地区：[1]贵州大学计算机科学与技术学院,贵州贵阳550025 [2]安顺学院电子与信息工程学院,贵州安顺561000

出　　处：《软件学报》2020年第4期1113-1123,共11页Journal of Software

基　　金：国家自然科学基金(61762019,61862051)。

摘　　要：研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.The study on the NP-completeness of regular SAT problem is a subject which has important theoretical value.It is proved that there is a critical function f(k)such that all formulas in(k,f(k))-CNF are satisfiable,but(k,f(k)+1)-SAT is NP-complete,and there is such a critical function about regular(k,s)-SAT problem too.This work studies the regular SAT problem with stronger regular constraints.The regular(k,s)-CNF is the subclass of CNF in which each clause of formula has exactly k distinct literals and each variable occurs exactly s times.The d-regular(k,s)-CNF is a regular(k,s)-CNF formula that the absolute value of the difference between positive and negative occurrence number of each variable in the formula is at most d.A polynomial reduction from a k-CNF formula is presented to a d-regular(k,s)-CNF formula and it is proved that there is a critical function f(k,d)such that all formulas in d-regular(k,f(k,d))-CNF are satisfiable,but d-regular(k,f(k,d)+1)-SAT is already NP-complete.By adding new variables and new clauses,the reduction method not only can alter the ration of clauses to variables of any one CNF formula,but also can restrict the difference between positive and negative occurrences number of each variable.This shows that only using constrained density(the ration of clauses to variables)to character structural features of a CNF formula is not enough.The study of the critical function f(k,d)is helpful to construct some hard instance under stronger regular constraints.

关 键 词：d-正则(k s)-CNF公式 SAT问题 NP完全性 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]