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

• 作者: 符祖峰 许道云
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: d-正则(k,s)-CNF公式 SAT问题 NP完全性
• 年，卷（期）: 2020,（4）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 1113-1123
• 页数: 11页
• 分类号: TP301
• 字数: 10225字
• 语种: 中文

摘要

研究具有正则结构的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)的研究有助于在更强正则约束条件下构造难解实例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与技术学院	125	460	12.0	16.0
2	符祖峰	贵州大学计算机科学与技术学院	31	35	4.0	5.0