%0 Journal Article
%T 一类可分离SAT问题的O(1.890n)精确算法
%A 王胜春
%A 黄金贵
%J -
%D 2018
%R 10.13328/j.cnki.jos.005378
%X 布尔可满足性问题（SAT）是指对于给定的布尔公式，是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题，一般认为不存在多项式时间算法，除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT），从全局搜索到局部搜索，给出了大量的相对有效算法，包括随机算法和确定算法.目前，最好算法的时间复杂度不超过O（（2-2/k）n），当k=3时，最好算法时间复杂度为O（1.308n）.而对于更一般的与子句长度k无关的SAT问题，很少有文献涉及.引入了一类可分离SAT问题，即3-正则可分离可满足性问题（3-RSSAT），证明了3-RSSAT是NP完全问题，给出了一般SAT问题3-正则可分离性的O（1.890n）判定算法.然后，利用矩阵相乘算法的研究成果，给出了3-RSSAT问题的O（1.890n）精确算法，该算法与子句长度无关
%K 可满足性问题 NP完全问题 正则可分离性 精确算法 算法复杂性
%U http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=5378&flag=1