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

被引：0

作者：

Fu Z.-F. ^{[1
,2
]}

Xu D.-Y. ^{[1
]}

机构：

[1] College of Computer Science and Technology, Guizhou University, Guiyang

[2] School of Electronic and Information Engineering, Anshun University, Anshun

来源：

Ruan Jian Xue Bao/Journal of Software | 2020年 / 31卷 / 04期

基金：

中国国家自然科学基金;

关键词：

d-regular; (k; s)-CNF; NP-completeness; SAT-problem;

D O I：

10.13328/j.cnki.jos.005896

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. © Copyright 2020, Institute of Software, the Chinese Academy of Sciences. All rights reserved.

引用

页码：1113 / 1123

页数：10

共 22 条

[11] Sumedha, Krishnamurthy S., Sahoo S., Balanced K-satisfiability and biased random K-satisfiability on trees, Physical Review E, 87, 4, (2013)
[12] Krishnamurthy S., Sumedha, Exact satisfiability threshold for k-satisfiability problems on a Bethe lattice, Physical Review E, 92, 4, (2015)
[13] Rathi V., Aurell E., Rasmussen L.K., Skoglund M., Bounds on threshold of regular random k-SAT, Lecture Notes in Computer Science, 6175, pp. 264-277, (2010)
[14] Zhou J.C., Xu D.Y., Lu Y.J., Satisfiability threshold of the regular random (k, r)-SAT problem, Ruan Jian Xue Bao/Journal of Software, 27, 12, pp. 2985-2993, (2016)
[15] Zhou J.C., Xu D.Y., Lu Y.J., Satisfiability threshold of regular (k, r)-SAT problem via 1RSB theory, Journal of Huazhong University of Science and Technology, 45, 12, pp. 7-13, (2017)
[16] Kratochvil J., Savicky P., Tuza Z., One more occurrence of variables makes satisfiability jump from trivial to NP-complete, SIAM Journal on Computing, 22, 1, pp. 203-210, (1993)
[17] Hoory S., Szeider S., Computing unsatisfiable k-SAT instances with few occurrences per variable, Theoretical Computer Science, 337, 1, pp. 347-359, (2005)
[18] Savicky P., Sgall J., DNF tautologies with a limited number of occurrences of every variable, Theoretical Computer Science, 238, 1, pp. 495-498, (2000)
[19] Gebauer H., Szabo T., Tardos G., The Local Lemma is asymptotically tight for SAT, Journal of the ACM, 63, 5, pp. 664-674, (2016)
[20] Hoory S., Szeider S., A note on unsatisfiable k-CNF formulas with few occurrences per variable, Society for Industrial and Applied Mathematics, pp. 523-528, (2006)

← 1 2 3 →