Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (5): 346-353.doi: 10.11896/jsjkx.250800047

• Artificial Intelligence • Previous Articles     Next Articles

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 Published: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)

153

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

CLC Number: 

  • 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.
[1] WANG Xianglong, WANG Yisong, XIE Zhongtao. Complexities of Logic Programs with Convex Aggregates [J]. Computer Science, 2025, 52(12): 209-214.
[2] HUANG Hua-wei, LI Chun-hua. Security Analysis of A Key Exchange Protocol Based on Tropical Semi-ring [J]. Computer Science, 2022, 49(6A): 571-574.
[3] HAN Jie, CHEN Jun-fen, LI Yan, ZHAN Ze-cong. Self-supervised Deep Clustering Algorithm Based on Self-attention [J]. Computer Science, 2022, 49(3): 134-143.
[4] YOU Ling, GUAN Zhang-jun. Low-complexity Subcarrier Allocation Algorithm for Underwater OFDM Acoustic CommunicationSystems [J]. Computer Science, 2021, 48(6A): 387-391.
[5] HE Bin, XU Dao-yun. Community Structure of Regular (3,4)-CNF Formula [J]. Computer Science, 2021, 48(4): 26-30.
[6] ZHU Kai, WU Guo-qing, YUAN Meng-ting. On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata [J]. Computer Science, 2020, 47(5): 14-21.
[7] YU Jian-jun, WU Chun-ming. Computational Complexity Analysis of Virtual Network Mapping Problem [J]. Computer Science, 2018, 45(11): 87-91.
[8] SHE Guang-wei, XU Dao-yun. Modified Warning Propagation Algorithm for Solving Regular (3,4)-SAT Instance Sets [J]. Computer Science, 2018, 45(11): 312-317.
[9] LU Zhao and ZHU Xiao-shu. Research on Image Processing Algorithm Based on Compressed Sensing [J]. Computer Science, 2017, 44(6): 312-316.
[10] CEN Yue-feng, WANG Wan-liang, YAO Xin-wei, WANG Chao-chao and PAN Tie-qiang. Decision Tree Based Coding Unit Splitting Algorithm for HEVC [J]. Computer Science, 2016, 43(4): 308-312.
[11] HE Kun,YAO Peng-cheng and LI Li-wen. Complete Algorithm for 2D Rectangular Packing Problem [J]. Computer Science, 2014, 41(8): 55-59.
[12] . Computational Complexity of Probabilistic Inference in Icing Graphical Model [J]. Computer Science, 2013, 40(2): 253-256.
[13] . [J]. Computer Science, 2007, 34(4): 158-162.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.