{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:13:50Z","timestamp":1760166830558,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In a regular (d,k)-CNF formula, each clause has length k and each variable appears d times. A regular structure such as this is symmetric, and the satisfiability problem of this symmetric structure is called the (d,k)-SAT problem for short. The regular exact 2-(d,k)-SAT problem is that for a (d,k)-CNF formula F, if there is a truth assignment T, then exactly two literals of each clause in F are true. If the formula F contains only positive or negative literals, then there is a satisfiable assignment T with a size of 2n\/k such that F is 2-exactly satisfiable. This paper introduces the (d,k)-SAT instance generation model, constructs the solution space, and employs the method of the first and second moments to present the phase transition point d* of the 2-(d,k)-SAT instance with only positive literals. When d&lt;d*, the 2-(d,k)-SAT instance can be satisfied with high probability. When d&gt;d*, the 2-(d,k)-SAT instance can not be satisfied with high probability. Finally, the verification results demonstrate that the theoretical results are consistent with the experimental results.<\/jats:p>","DOI":"10.3390\/sym13071231","type":"journal-article","created":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T21:05:54Z","timestamp":1625778354000},"page":"1231","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Phase Transition Analysis for the Random Regular Exact 2-(d, k)-SAT Problem"],"prefix":"10.3390","volume":"13","author":[{"given":"Guoxia","family":"Nie","sequence":"first","affiliation":[{"name":"College of Computer Science and Technology, Guizhou University, Guiyang 550025, China"}]},{"given":"Daoyun","family":"Xu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Guizhou University, Guiyang 550025, China"}]},{"given":"Xiaofeng","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China"},{"name":"Ningxia Key Laboratory of Intelligent Information and Big Data Processing, Yinchuan 750021, China"}]},{"given":"Xi","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Guizhou University, Guiyang 550025, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,8]]},"reference":[{"key":"ref_1","first-page":"98","article-title":"Reduction Techniques for Satisfiability Problems","volume":"5","author":"Xu","year":"2012","journal-title":"Stud. Logic."},{"key":"ref_2","first-page":"691","article-title":"A regular NP-complete problem and it\u2019s inaproximability","volume":"7","author":"Xu","year":"2013","journal-title":"J. Front. Comput. Sci. Technol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","article-title":"Critical behavior in the satisfiability of random Boolean Formulae","volume":"264","author":"Kirkpatrick","year":"1994","journal-title":"Science"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1002\/rsa.20090","article-title":"Threshold values of random k-SAT from the cavity method","volume":"28","author":"Mertens","year":"2006","journal-title":"Random Struct. Algorithms"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"10318","DOI":"10.1073\/pnas.0703685104","article-title":"Gibbs states and the set of solutions of random constraint satisfaction Problems","volume":"104","author":"Montanari","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.artint.2010.11.004","article-title":"On the phase transitions of random k-constraint satisfaction problems","volume":"175","author":"Fan","year":"2011","journal-title":"Artif. Intell."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1002\/rsa.20104","article-title":"The probabilistic analysis of a greedy satisfiability algorithm","volume":"28","author":"Kaporis","year":"2006","journal-title":"Random Struct. Algorithms"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2920","DOI":"10.1016\/j.tcs.2009.02.020","article-title":"On the satisfiability threshold of formulas with three literals per clause","volume":"410","author":"Kirousis","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","first-page":"1","article-title":"Comparing beliefs, surveys, and random walks","volume":"17","author":"Aurell","year":"2004","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/978-3-540-24605-3_38","article-title":"Survey and belief propagation on random k-SAT","volume":"2919","author":"Braunstein","year":"2004","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s10817-005-9012-z","article-title":"Regular random k-sat: Properties of balanced formulas","volume":"35","author":"Boufkhad","year":"2005","journal-title":"J. Autom. Reason."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/978-3-642-14186-7_22","article-title":"Bounds on Threshold of Regular Random k-SAT","volume":"6175","author":"Rathi","year":"2010","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_13","unstructured":"Jian, D., Sly, A., and Nike, S. (June, January 31). Satisfiability threshold for random regular NAE-SAT. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA."},{"key":"ref_14","unstructured":"Achlioptas, D., Chtcherba, A., Istrate, G., and Moore, C. (2001, January 7\u20139). The phase transition in 1-in-k SAT and NAE 3-SAT. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/S0097539703434231","article-title":"RANDOM k-SAT: Two moments suffice to cross a sharp threshold","volume":"36","author":"Achioptas","year":"2006","journal-title":"SIAM J. Comput."},{"key":"ref_16","first-page":"349","article-title":"The phase transition in random regular exact cover","volume":"3","author":"Moore","year":"2016","journal-title":"Annales l\u2019Institut Henri Poincar\u00e9 D"},{"key":"ref_17","first-page":"9","article-title":"The phase transition in exact cover","volume":"5","author":"Kalapala","year":"2008","journal-title":"Chic. J. Theor. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"26664","DOI":"10.1109\/ACCESS.2021.3057858","article-title":"The Phase Transition Analysis for Random Regular Exact (s,c,k)-SAT Problem","volume":"9","author":"Mo","year":"2021","journal-title":"IEEE Access"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., and Upfal, E. (2005). Probability and Computing, Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/7\/1231\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:28:03Z","timestamp":1760164083000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/7\/1231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,8]]},"references-count":19,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2021,7]]}},"alternative-id":["sym13071231"],"URL":"https:\/\/doi.org\/10.3390\/sym13071231","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2021,7,8]]}}}