{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T20:18:52Z","timestamp":1758399532638},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,7,11]],"date-time":"2020-07-11T00:00:00Z","timestamp":1594425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,11]],"date-time":"2020-07-11T00:00:00Z","timestamp":1594425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s11704-020-9248-0","type":"journal-article","created":{"date-parts":[[2020,7,11]],"date-time":"2020-07-11T04:35:11Z","timestamp":1594442111000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Properties of the satisfiability threshold of the strictly d-regular random (3,2s)-SAT problem"],"prefix":"10.1007","volume":"14","author":[{"given":"Yongping","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daoyun","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,11]]},"reference":[{"key":"9248_CR1","doi-asserted-by":"crossref","unstructured":"Cook S A. The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. 1971, 151\u2013158","DOI":"10.1145\/800157.805047"},{"issue":"4","key":"9248_CR2","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E Friedgut","year":"1999","unstructured":"Friedgut E, Bourgain J. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the American Mathematical Society, 1999, 12(4): 1017\u20131054","journal-title":"Journal of the American Mathematical Society"},{"issue":"4","key":"9248_CR3","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"A C Kaporis","year":"2006","unstructured":"Kaporis A C, Kirousis L M, Lalas E G. The probabilistic analysis of a greedy satisfiability algorithm. Random Structures & Algorithms, 2006, 28(4): 444\u2013480","journal-title":"Random Structures & Algorithms"},{"issue":"30\u201332","key":"9248_CR4","doi-asserted-by":"publisher","first-page":"2920","DOI":"10.1016\/j.tcs.2009.02.020","volume":"410","author":"J D\u00edaz","year":"2009","unstructured":"D\u00edaz J, Kirousis L, Mitsche D, P\u00e9rez-Gim\u00e9nez X. On the satisfiability threshold of formulas with three literals per clause. Theoretical Computer Science, 2009, 410(30\u201332): 2920\u20132934","journal-title":"Theoretical Computer Science"},{"key":"9248_CR5","unstructured":"Mitchell D, Selman B, Levesque H. Hard and easy distributions of SAT problems. In: Proceedings of the 10th National Conference on Artificial Intelligence. 1992, 459\u2013465"},{"issue":"1\u20132","key":"9248_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0004-3702(95)00046-1","volume":"81","author":"J M Crawford","year":"1996","unstructured":"Crawford J M, Auton L D. Experimental results on the crossover point in random 3-SAT. Artificial Intelligence, 1996, 81(1\u20132): 31\u201357","journal-title":"Artificial Intelligence"},{"issue":"6740","key":"9248_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1999","unstructured":"Monasson R, Zecchina R, Kirkpatrick S, Selman B, Troyansky L. Determining computational complexity from characteristic\u2019 phase transitions\u2019. Nature, 1999, 400(6740): 133\u2013137","journal-title":"Nature"},{"issue":"2","key":"9248_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A Braunstein","year":"2002","unstructured":"Braunstein A, M\u00e9zard M, Zecchina R. Survey propagation: an algorithm for satisfiability. Random Structures & Algorithms, 2002, 27(2): 201\u2013226","journal-title":"Random Structures & Algorithms"},{"issue":"8","key":"9248_CR9","first-page":"691","volume":"7","author":"D Xu","year":"2013","unstructured":"Xu D, Wang X. A regular NP-complete problem and its inapproximability. Journal of Frontiers of Computer Science and Technology, 2013, 7(8): 691\u2013697 (In Chinese)","journal-title":"Journal of Frontiers of Computer Science and Technology"},{"issue":"1\u20133","key":"9248_CR10","first-page":"181","volume":"35","author":"Y Boufkhad","year":"2005","unstructured":"Boufkhad Y, Dubois O, Interian Y, Selman B. Regular random k-SAT: properties of balanced formulas. Journal of Automated Reasoning, 2005, 35(1\u20133): 181\u2013200","journal-title":"Journal of Automated Reasoning"},{"key":"9248_CR11","doi-asserted-by":"crossref","unstructured":"Rathi V, Aurell E, Rasmussen L, Skoglund M. Bounds on threshold of regular random k-SAT In: Proceedings of the 13th International Conference on Theory & Applications of Satisfiability Testing. 2010, 264\u2013277","DOI":"10.1007\/978-3-642-14186-7_22"},{"issue":"12","key":"9248_CR12","first-page":"2563","volume":"42","author":"J Zhou","year":"2016","unstructured":"Zhou J, Xu D, Lu Y, Dai C. Strictly regular random (3, s)-SAT model and its phase transition phenomenon. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(12): 2563\u20132571 (In Chinese)","journal-title":"Journal of Beijing University of Aeronautics and Astronautics"},{"issue":"1\u20133","key":"9248_CR13","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0012-365X(94)00133-4","volume":"139","author":"D Gardy","year":"1995","unstructured":"Gardy D. Some results on the asymptotic behaviour of coefficients of large powers of functions. Discrete Mathematics, 1995, 139(1\u20133): 189\u2013217","journal-title":"Discrete Mathematics"},{"key":"9248_CR14","doi-asserted-by":"crossref","unstructured":"Mahajan Y S, Fu Z, Malik S. Zchaff2004: an efficient SAT solver. In: Proceedings of the 7th International Conference on Theory & Applications of Satisfiability Testing. 2004, 360\u2013375","DOI":"10.1007\/11527695_27"},{"issue":"12","key":"9248_CR15","first-page":"2985","volume":"27","author":"J C Zhou","year":"2016","unstructured":"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, 2016, 27(12): 2985\u20132993 (In Chinese)","journal-title":"Ruan Jian Xue Bao\/Journal of Software"},{"issue":"4","key":"9248_CR16","doi-asserted-by":"publisher","first-page":"042130","DOI":"10.1103\/PhysRevE.87.042130","volume":"87","author":"Sumedha","year":"2013","unstructured":"Sumedha, Krishnamurthy S, Sahoo S. Balanced k-satisfiability and biased random k-satisfiability on trees. Physical Review E, 2013, 87(4): 042130","journal-title":"Physical Review E"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-020-9248-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-020-9248-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-020-9248-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T21:18:22Z","timestamp":1642627102000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-020-9248-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,11]]},"references-count":16,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["9248"],"URL":"https:\/\/doi.org\/10.1007\/s11704-020-9248-0","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,11]]},"assertion":[{"value":"8 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"146404"}}