{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T07:23:43Z","timestamp":1777706623725,"version":"3.51.4"},"reference-count":20,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2024,4,2]],"date-time":"2024-04-02T00:00:00Z","timestamp":1712016000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology"],"published-print":{"date-parts":[[2025,8]]},"abstract":"\n A CNF formula with each clause of length k and each variable occurring 4\n s<\/jats:italic>\n times, where positive occurrences are 3\n s<\/jats:italic>\n and negative occurrences are\n s<\/jats:italic>\n , is a regular (3\n s<\/jats:italic>\n \u00a0+\u00a0\n s<\/jats:italic>\n ,\n k<\/jats:italic>\n )-CNF formula (\n F<\/jats:italic>\n \n 3\n s<\/jats:italic>\n +\n s<\/jats:italic>\n ,\n k<\/jats:italic>\n <\/jats:sub>\n formula). The random regular exact (3\n s<\/jats:italic>\n \u00a0+\u00a0\n s<\/jats:italic>\n ,\n k<\/jats:italic>\n )-SAT problem is whether there exists a set of Boolean variable assignments such that exactly one literal is true for each clause in the\n F<\/jats:italic>\n \n 3\n s<\/jats:italic>\n +\n s<\/jats:italic>\n ,\n k<\/jats:italic>\n <\/jats:sub>\n formula. By introducing a random instance generation model, the satisfiability phase transition of the solution is analyzed by using the first moment method, the second moment method, and the small subgraph conditioning method, which gives the phase transition point\n s*<\/jats:italic>\n of the random regular exact (3\n s<\/jats:italic>\n \u00a0+\u00a0\n s<\/jats:italic>\n ,\n k<\/jats:italic>\n )-SAT problem for\n k<\/jats:italic>\n \u22653. When\n s<\/jats:italic>\n \u200a<\u200a\n s*<\/jats:italic>\n ,\n F<\/jats:italic>\n \n 3\n s<\/jats:italic>\n +\n s<\/jats:italic>\n ,\n k<\/jats:italic>\n <\/jats:sub>\n formula is satisfiable with high probability; when\n s<\/jats:italic>\n \u200a>\u200a\n s*<\/jats:italic>\n ,\n F<\/jats:italic>\n \n 3\n s<\/jats:italic>\n +\n s<\/jats:italic>\n ,\n k<\/jats:italic>\n <\/jats:sub>\n formula is unsatisfiable with high probability. Finally, through the experimental verification, the results show that the theoretical proofs are consistent with the experimental results.\n <\/jats:p>","DOI":"10.3233\/jifs-238254","type":"journal-article","created":{"date-parts":[[2024,4,2]],"date-time":"2024-04-02T13:59:07Z","timestamp":1712066347000},"page":"340-350","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["The phase transition in random regular exact (3\n s<\/i>\n \u00a0+\u00a0\n s<\/i>\n ,\n k<\/i>\n )-SAT problem"],"prefix":"10.1177","volume":"49","author":[{"given":"Ao","family":"Tang","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofeng","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan, China"},{"name":"The Key Laboratory of Images & Graphics Intelligent Processing of State Ethnic Affairs Commission, North Minzu University, Yinchuan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingyuan","family":"Peng","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junxia","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"He","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yingying","family":"Hua","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, North Minzu University, Yinchuan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2024,4,2]]},"reference":[{"key":"e_1_3_2_2_1","unstructured":"AchlioptasD.ChtcherbaA.IstrateG.MooreC. The phase transition in 1-in-k SAT and NAE 3-SAT[J] ACM Symposium on Discrete Algorithms (2001) 721\u2013722."},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434231"},{"key":"e_1_3_2_4_1","doi-asserted-by":"crossref","unstructured":"Coja-OglanA.PanagiotouK. Catching the k-NAESAT threshold[C]\/\/ Proceedings of the fortyfourth annual ACM symposium on Theory of computing ACM (2012) 899\u2013908.","DOI":"10.1145\/2213977.2214058"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2492-8"},{"key":"e_1_3_2_6_1","unstructured":"KnyshS.SmelyanskiyV.N.MorrisR.D. Approximating satisfiability transition by suppressing fluctuations[J] arXiv preprint cond-mat\/0403416 2004"},{"key":"e_1_3_2_7_1","unstructured":"KalapalaV.MooreC. The phase transition in exact cover[J] Chicago Journal of Theoretical Computer Science (2008) 5."},{"issue":"3","key":"e_1_3_2_8_1","first-page":"349","article-title":"The phase transition in random regular exact cover[J]","volume":"3","author":"Moore C.","year":"2016","unstructured":"MooreC., The phase transition in random regular exact cover[J], Ann. Inst.3(3) (2016), 349\u2013362","journal-title":"Ann. Inst."},{"key":"e_1_3_2_9_1","unstructured":"PanagiotouK.PaschM. Satisfiability thresholds for regular occupation problems[J] arXiv preprint arXiv:1811.00991 2018."},{"issue":"02","key":"e_1_3_2_10_1","first-page":"105","article-title":"Phase transition of in random balance regular exact (2s,k)-SAT problem [J]","volume":"50","author":"Wang X.F.","year":"2022","unstructured":"WangX.F.YuZ.ZhouJ.C., et al. Phase transition of in random balance regular exact (2s,k)-SAT problem [J], Journal of Huazhong University of Science and Technology (Natural Science Edition)50(02) (2022), 105\u2013111.","journal-title":"Journal of Huazhong University of Science and Technology (Natural Science Edition)"},{"key":"e_1_3_2_11_1","doi-asserted-by":"crossref","unstructured":"WormaldN.C. Models of random regular graphs[J] London Mathematical Society Lecture Note Series (1999) 239\u2013298.","DOI":"10.1017\/CBO9780511721335.010"},{"issue":"4","key":"e_1_3_2_12_1","first-page":"1113","article-title":"NP-completeness of d-regular (k,s)-SAT problem","volume":"31","author":"Fu Z.F.","year":"2020","unstructured":"FuZ.F.XuD.Y., NP-completeness of d-regular (k,s)-SAT problem, Ruan Jian Xue Bao\/Journal of Software31(4) (2020), 1113\u20131123.","journal-title":"Ruan Jian Xue Bao\/Journal of Software"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434231"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms12996"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000251"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3096-x"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"issue":"9","key":"e_1_3_2_18_1","first-page":"2629","article-title":"Satisfiability threshold of strictly d-regular random (3,2s)-SAT problem for fixed s","volume":"32","author":"Wang Y.P.","year":"2021","unstructured":"WangY.P.XuD.Y., Satisfiability threshold of strictly d-regular random (3,2s)-SAT problem for fixed s, Ruan Jian Xue Bao\/Journal of Software32(9) (2021), 2629\u20132641.","journal-title":"Ruan Jian Xue Bao\/Journal of Software"},{"key":"e_1_3_2_19_1","doi-asserted-by":"crossref","unstructured":"NamD.SlyA.SohnY. One-step replica symmetry breaking of random regular NAE-SAT[C]\/\/2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) IEEE (2022) 310\u2013318.","DOI":"10.1109\/FOCS52979.2021.00039"},{"key":"e_1_3_2_20_1","doi-asserted-by":"crossref","unstructured":"NieG.XuD.WangX. et al.The Phase Transition Analysis for the Random Regular Exact 2-(d k)-SAT Problem[J] Symmetry 2021 https:\/\/doi.org\/10.3390\/sym13071231.","DOI":"10.3390\/sym13071231"},{"issue":"11","key":"e_1_3_2_21_1","first-page":"1852","article-title":"Probabilistic Properties of Satisfiable Solutions on Space of Assignments for CNF Formula[J]","volume":"12","author":"Mo Xiao-ling","year":"2018","unstructured":"Mo Xiao-lingXu Dao-yun,Probabilistic Properties of Satisfiable Solutions on Space of Assignments for CNF Formula[J], Journal of Frontiers of Computer Science & Technology12(11) (2018), 1852\u20131861.","journal-title":"Journal of Frontiers of Computer Science & Technology"}],"container-title":["Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-238254","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JIFS-238254","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-238254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:47:23Z","timestamp":1777456043000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JIFS-238254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,2]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.3233\/JIFS-238254"],"URL":"https:\/\/doi.org\/10.3233\/jifs-238254","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,2]]}}}