d-正则(k,s)-SAT问题的NP完全性
作者:
作者单位:

作者简介:

符祖峰(1978-),男,河南南阳人,副教授,主要研究领域为计算复杂性,可计算性分析;许道云(1959-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为计算复杂性,可计算性分析.

通讯作者:

中图分类号:

TP301

基金项目:

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


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

Fund Project:

National Natural Science Foundation of China (61762019, 61862051)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(ks)-CNF公式类和正则(ks)-CNF公式类已被证明存在一个临界函数fk),使得当sfk)时,所有实例都可满足;当sfk)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(ks)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(ks)-SAT问题存在一个临界函数fkd),使得当sfkd)时,所有实例都可满足;当sfkd)+1时,d-正则(ks)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数fkd)的研究有助于在更强正则约束条件下构造难解实例.

    Abstract:

    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)-SAT问题的NP完全性.软件学报,2020,31(4):1113-1123

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2019-04-24
  • 最后修改日期:2019-11-03
  • 录用日期:
  • 在线发布日期: 2020-04-16
  • 出版日期: 2020-04-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号