一类可分离SAT问题的O(1.890n)精确算法

• 作者: 王胜春 黄金贵
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 可满足性问题 NP完全问题 正则可分离性 精确算法 算法复杂性
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 3595-3603
• 页数: 9页
• 分类号: TP301
• 字数: 9218字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005378

摘要

布尔可满足性问题(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)精确算法,该算法与子句长度无关.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王胜春	湖南师范大学信息科学与工程学院	14	160	5.0	12.0
2	黄金贵	湖南师范大学信息科学与工程学院	14	69	5.0	8.0