计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (5): 346-353.doi: 10.11896/jsjkx.250800047

• 人工智能 • 上一篇    下一篇

严格d-正则(3,s)-SAT问题的计算复杂性

王永平1, 符祖峰2   

  1. 1 贵州财经大学信息学院算法与计算复杂性实验室 贵阳 550025
    2 南阳师范学院人工智能与软件工程学院 河南 南阳 473061
  • 收稿日期:2025-08-11 修回日期:2025-11-12 发布日期:2026-05-08
  • 通讯作者: 王永平(wangyp_gc@mail.gufe.edu.cn)
  • 基金资助:
    国家自然科学基金(62362007)

Computational Complexity of Strictly d-regular (3,s)-SAT Problem

WANG Yongping1, FU Zufeng2   

  1. 1 Algorithm and Computational Complexity Laboratory of School of Information, Guizhou University of Finance and Economics, Guiyang 550025, China
    2 School of Artificial Intelligence and Software Engineering, Nanyang Normal University, Nanyang, Henan 473061, China
  • Received:2025-08-11 Revised:2025-11-12 Online:2026-05-08
  • About author:WANG Yongping,born in 1980,Ph.D,associate professor,master’s supervisor.His main research interests include computational complexity and algorithm design and analysis.
  • Supported by:
    National Natural Science Foundation of China(62362007).

PDF (PC)

178

摘要： 严格d-正则(3,s)-SAT问题是指:给定一个严格d-正则(3,s)-CNF公式,判定是否存在对其变量的一个真值指派,使公式的真值为真。此处,严格d-正则(3,s)-CNF公式是指:每个子句的长度为3,每个变量的出现次数为s,每个变量的正、负出现次数之差的绝对值为d 的CNF公式。研究表明,一定条件下,严格d-正则(3,s)-SAT问题存在难解实例聚集现象。因此,讨论了严格d-正则(3,s)-SAT问题的计算复杂性,证明了:当 s≥4 时,存在不可满足的严格(s－2)-正则(3,s)-CNF公式和不可满足的严格(s－4)-正则(3,s)-CNF公式。由此,已有的系列结论中的假设条件成为现实。于是,严格d-正则(3,s)-SAT问题的计算复杂性得以解决:当 s≤3 时,严格d-正则(3,s)-CNF公式均可满足;当s≥4 且d<s时,严格d-正则(3,s)-SAT问题是NP-完全问题;当 s≥4 且d=s时,严格d-正则(3,s)-CNF公式均可满足。需指出,所得结论意味着,严格0-正则(3,4)-SAT问题和严格2-正则(3,4)-SAT问题均是NP-完全问题,即严格0-正则(3,4)-SAT问题和严格2-正则(3,4)-SAT问题保留了正则(3,4)-SAT问题的NP-完全性,也保留了3-SAT问题的NP-完全性。因此,继续研究严格d-正则(3,s)-SAT问题,尤其是严格0-正则(3,4)-SAT问题和严格2-正则(3,4)-SAT问题应该是必要的。

关键词: 3-SAT问题, 正则(3,s)-SAT问题, 严格d-正则(3,s)-SAT问题, 计算复杂性, NP-完全类

Abstract: he strictly d-regular (3,s)-SAT problem determines whether a given strictly d-regular (3,s)-CNF formula is satisfiable,where a CNF formula is satisfiable if there exists a truth assignment to its variables such that the truth value of the formula is true.A CNF formula is a 3-CNF formula if each clause contains three literals;a 3-CNF formula is a regular (3,s)-CNF formula if each variable appears s times in the formula;and a regular (3,s)-CNF formula is a strictly d-regular (3,s)-CNF formula if the absolute value of the difference between the positive and negative occurrences of each variable is d.Existing research shows that the strictly d-regular (3,s)-SAT problem has an aggregation phenomenon of hard-solving instances under some conditions.Hence,this paper studies the computational complexity of the strictly d-regular (3,s)-SAT problem.It shows that there exists both an unsatisfiable strictly (s-2)-regular (3,s)-CNF formula and an unsatisfiable strictly(s-4)-regular(3,s)-CNF formula when s≥4.Thus,the assumptions underlying the existing series of conclusions are confirmed.Hence,it determines the computational complexity of the strictly d-regular (3,s)-SAT problem as follows.A strictly d-regular (3,s)-CNF formula is satisfiable when s≤3;the strictly d-regular (3,s)-SAT problem is NP-complete when s≥4 and d<s;and a strictly d-regular (3,s)-CNF formula is satisfiable when s≥4 and d＝s.It is necessary to say that both the strictly 0-regular (3,4)-SAT problem and the strictly 2-regular (3,4)-SAT problem are NP-complete by the conclusion above.In other words,the strictly 0-regular (3,4)-SAT problem and the strictly 2-regular (3,4)-SAT problem inherit the NP-completeness of both the regular (3,4)-SAT problem and the 3-SAT problem.So,it should be necessary to study further the strictly d-regular (3,s)-SAT problem,especially,to study the strictly 0-regular (3,4)-SAT problem and the strictly 2-regular (3,4)-SAT problem.

Key words: 3-SAT problem, Regular (3, s)-SAT problem, Strictly d-regular (3, s)-SAT problem, Computational complexity, NP-complete class

中图分类号: 

  • TP301.5
[1]YU Z Q,ZHANG X Y,LI J W.UC-based Approximate Incremental Reachability[J].Ruan Jian Xue Bao/Journal of Software,2023,34(8):3467-3484.
[2]CAI S W,CHEN Z B,WANG J,et al.Preface to the Special Topic of Constraint Solving and Theorem Proving[J].Ruan Jian Xue Bao/Journal of Software,2023,34(8):3465-3466.
[3]DAWN M,DOMINIK S,MARIJN J H H,et al.Unsatisfiability Proofs for Distributed Clause-sharing SAT Solvers[C]//Proceedings,Part I,of the 29th International Conference on Tools and Algorithms for the Construction and Analysis of Systems.Cham:Springer,2023:348-366.
[4]COOK S A.The Complexity of Theorem-proving Procedures[C]//Proceedings of the 3rd Annual ACM Symposium on Theory of Computing.New York:ACM,1971:151-158.
[5]DECHTER R,PEARL J.Network-based Heuristics for Con-straint-satisfaction Problems[J].Artificial Intelligence,1987,34(1):1-38.
[6]ASPVALL B,PLASS M F,TARJAN R.A Linear-time Algorithm for Testing the Truth of Certain Quantified Boolean Problems[J].Information Processing Letters,1979,8(3):121-123.
[7]FU H M,XU Y,CHEN S W,et al.Improving WalkSAT for Random 3-SAT Problems[J].Journal of Universal Computer Science,2020,26(2):220-243.
[8]ZHU J Y,SALHOTRA A,MEINECKE C R,et al.Solving the 3-satisfiability Problem Using Network-based Biocomputation[J].Advanced Intelligent Systems,2022,4:2200202.
[9]CILASUN H,ZENG Z Q,RAMPRASATH S,et al.3SAT on an All-to-all-connected CMOS Ising Solver Chip[J].Scientific Reports,2024,14:10757.
[10]TOVEY C A.A Simplified NP-complete Satisfiability Problem[J].Discrete Applied Mathematics,1984,8(1):85-89.
[11]KRATOCHVIL J,SAVICKY P,TUZA Z.One More Occur-rence of Variables Makes Satisfiability Jump from Trivial to NP-complete[J].SIAM Journal of Computing,1993,22(1):203-210.
[12]MITCHELL D,SELMAN B,LEVESQUE H.Hard and Easy Distributions of SAT Problems[C]//Proceedings of the 10th National Conference on Artificial Intelligence.California:AAAI,1992:459-465.
[13]CRAWFORD J M,AUTON L D.Experimental Results on the Crossover Point in Random 3-SAT[J].SIAM Journal on Computing,1993,22(1):203-210.
[14]SELMAN B,KIRKPATRICK S.Critical Behavior in the Computational Cost of Satisfiability Testing[J].Artificial Intelligence,1996,81(1／2):273-295.
[15]BRAUNSTEIN A,MEZARD M,ZECCHINA R.Survey Propagation:an Algorithm for Satisfiability[J].Random Structures & Algorithms,2005,27(2):201-226.
[16]ZHOU J C,XU D Y,LU Y J,et al.Strictly Regular Random (3,s)-SAT Model and Its Phase Transition Phenomenon[J].Journal of Beijing University of Aeronautics and Astronautics,2016,42(12):2563-2571.
[17]SUMEDHA,KRISHNAMURTHY S,SAHOO S.Balanced K-satisɦability and Biased Random K-satisfiability on Trees[J].Physical Review E,2013,87(4):042130.
[18]WANG Y P,XU D Y.Satisfiability Threshold of the strictly d-regular Random (3,2s)-SAT Problem for Fixed s[J].Ruan Jian Xue Bao/Journal of Software,2021,32(9):2629-2641.
[19]WANG Y P,XU D Y.Satisfiability Threshold of the strictly d-regular Random (3,s)-SAT Problem[C]//Proceedings of the 2020 International Conference on Big Data & Artificial Intelligence & Software Engineering.Washington DC:IEEE Computer Society,2020:419-424.
[20]MAHAJAN Y S,FU Z,MALIK S.Zchaff2004:an Efficient SAT Solver[C]//Revised Selected Papers of the 7th International Conference on Theory & Applications of Satisfiability Testing.Berlin:Springer,2004:360-375.
[21]WANG Y P,XU D Y.Properties of the Satisfiability Threshold of the strictly d-regular Random (3,2s)-SAT Problem[J].Frontiers of Computer Science,2020,14(6):146404.
[22]WANG Y P.Research on the Satisfiability of the strictly d-regular Random (3,s)-CNF Formula[D].Guiyang:Guizhou University,2020.
[23]FU Z F,XU D Y.NP-completeness of d-regular (k,s)-SAT Problem[J].Ruan Jian Xue Bao/Journal of Software,2020,31(4):1113-1123.
[24]FU Z F.The Critical Phenomenon and Structure Characteristics of d-regular (k,s)-SAT Problem[D].Guiyang:Guizhou University,2020.
[25]MO X L,XU D Y,YAN K,et al.Satisfiability Threshold of the Random Regular (s,c,k)-SAT Problem[J].Frontiers of Computer Science,2022,16(3):163408.
[26]RAY-CHAUDHURI D K,WILSON R M.Solution of Kirkman’sSchoolgirl Problem[C]//Proceedings of the Symposium in Pure Mathematics of the American Mathematical Society.Rhode Island:AMS,1968:187-203.
[27]LINDNER C C,RODGER C A.Design Theory[M].New York:CRC Press,1997:71-72.
[28]SHEN N,XU F.In Memory of the Master of CombinatorialMathematics Lu Jiaxi[J].Journal of Dialectics of Nature,2024,46(9):111-116.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发