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

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

中图分类号:

TP301

基金项目:

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


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

National Natural Science Foundation of China (61762019, 61862051)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [26]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    研究具有正则结构的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.

    参考文献
    [1] Cook SA. The complexity of theorem-proving procedures. In:Proc. of the 3rd Annual ACM Symp. on Theory of Computing. New York:ACM Press, 1971. 151-158.[doi:10.1145/800157.805047]
    [2] Xu DY, Wang XF. A regular NP-complete problem and its inapproximability. Journal of Frontiers of Computer Science & Technology, 2013,7(8):691-697(in Chinese with English abstract).[doi:10.3778/j.issn.1673-9418.1305025]
    [3] Crawford JM, Auton LD. Experimental results on the crossover point in satisfiability problems. In:Proc. of the 11th National Conf. on Artificial Intelligence. Washington:AAAI Press, 1993. 21-27.[doi:10.1016/0004-3702(95)00046-1]
    [4] Kirkpatrick S, Selman B. Critical behavior in the satisfiability of random boolean expressions. Science, 1994,264(5163):1297-1301.[doi:10.1126/science.264.5163.1297]
    [5] Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. Journal of Artiial Intelligene Researh, 2000,12:93-103.[doi:10.1613/jair.696]
    [6] Xu K, Li W. Many hard examples in exact phase transitions. Theoretical Computer Science, 2006,355(3):291-302.[doi:10.1016/j.tcs.2006.01.001]
    [7] Liu T, Lin X, Wang C, et al. Large hinge width on sparse random hypergraphs. In:Proc. of the 22nd Int'l Joint Conf. on Artificial Intelligence. Washington:AAAI Press, 2011.[doi:10.5591/978-1-57735-516-8/IJCAI11-109]
    [8] Liu T, Wang C, Xu W. Balanced random constraint satisfaction:Phase transition and hardness. In:Chen J, Lu P, eds. Frontiers in Algorithmics. Berlin, Heidelberg:Springer-Verlag, 2018. 238-250.[doi:10.1007/978-3-319-78455-7_18]
    [9] Mézard M, Parisi G, Zecchina R. Analytic and algorithmic solution of random satisfiability problems. Science, 2002,297(5582):812-815.[doi:10.1126/science.1073287]
    [10] Boufkhad Y, Dubois O, Interian Y, Selman B. Regular random k-SAT:Properties of balanced formulas. Journal of Automated Reasoning, 2005,1(35):181-200.[doi:10.1007/s10817-005-9012-z]
    [11] Sumedha, Krishnamurthy S, Sahoo S. Balanced K-satisfiability and biased random K-satisfiability on trees. Physical Review E, 2013,87(4):042130.[doi:10.1103/PhysRevE.87.042130]
    [12] Krishnamurthy S, Sumedha. Exact satisfiability threshold for k-satisfiability problems on a Bethe lattice. Physical Review E, 2015, 92(4):042144.[doi:10.1103/PhysRevE.92.042144]
    [13] Rathi V, Aurell E, Rasmussen LK, Skoglund M. Bounds on threshold of regular random k-SAT. In:Strichman O, Szeider S, eds. Lecture Notes in Computer Science. Berlin, Heidelberg:Springer-Verlag, 2010,6175:264-277.[doi:10.1007/978-3-642-14186-7_22]
    [14] Zhou JC, Xu DY, Lu YJ. Satisfiability threshold of the regular random (k,r)-SAT problem. Ruan Jian Xue Bao/Journal of Software, 2016,27(12):2985-2993(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5129.htm[doi:10.13328/j.cnki.jos. 005129]
    [15] Zhou JC, Xu DY, Lu YJ. Satisfiability threshold of regular (k,r)-SAT problem via 1RSB theory. Journal of Huazhong University of Science and Technology, 2017,45(12):7-13(in Chinese with English abstract).[doi:10.13245/j.hust.171202]
    [16] Kratochvíl J, Savický P, Tuza Z. One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM Journal on Computing, 1993,22(1):203-210.[doi:10.1137/0222015]
    [17] Hoory S, Szeider S. Computing unsatisfiable k-SAT instances with few occurrences per variable. Theoretical Computer Science, 2005,337(1):347-359.[doi:10.1016/j.tcs.2005.02.004]
    [18] Savický P, Sgall J. DNF tautologies with a limited number of occurrences of every variable. Theoretical Computer Science, 2000,238(1):495-498.[doi:10.1016/s0304-3975(00)00036-0]
    [19] Gebauer H, Szabo T, Tardos G. The Local Lemma is asymptotically tight for SAT. Journal of the ACM, 2016,63(5):664-674.[doi:10.1145/2975386]
    [20] Hoory S, Szeider S. A note on unsatisfiable k-CNF formulas with few occurrences per variable. Society for Industrial and Applied Mathematics, 2006. 523-528.[doi:10.1137/S0895480104445745]
    [21] Tovey CA. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 1984,8(1):85-89.[doi:10.1016/0166-218x(84)90081-7]
    [22] Davydov G, Davydova I, Büning HK. An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF. Annals of Mathematics & Artificial Intelligence, 1998,23(3-4):229-245.[doi:10.1023/A:1018924526592]
    附中文参考文献:
    [2] 许道云,王晓峰.一个正则NP-完全问题及其不可近似性.计算机科学与探索,2013,7(8):691-697.[doi:10.3778/j.issn.1673-9418. 1305025]
    [14] 周锦程,许道云,卢友军.随机正则(k,r)-SAT问题的可满足临界.软件学报,2016,27(12):2985-2993. http://www.jos.org.cn/1000-9825/5129.htm[doi:10.13328/j.cnki.jos.005129]
    [15] 周锦程,许道云,卢友军.基于1 RSB的正则(k,r)-SAT问题可满足临界.华中科技大学学报(自然科学版),2017,45(12):7-13.[doi:10.13328/j.cnki.jos.005129]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

符祖峰,许道云.d-正则(k,s)-SAT问题的NP完全性.软件学报,2020,31(4):1113-1123

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

京公网安备 11040202500063号