{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:40Z","timestamp":1759638700329},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p> The random (2 + p)-SAT model has been proposed [18] to study the possible relation between the \u201corder\u201d of phase transitions and computational complexity. It was also claimed that there exists p<jats:sub>c<\/jats:sub> &gt; 0, such that for p &lt; p<jats:sub>c<\/jats:sub> the random (2 + p)-SAT instance behaves like 2-SAT. Later, Achlioptas et al. [3] obtained the first rigorous results that 0.4 \u2264 p<jats:sub>c<\/jats:sub> \u2264 0.695, the methods they use are the first moment method and the simple Unit-Clause algorithm. In this paper, we try to optimize the local maximality condition of the truth assignments when implementing the first moment method. We prove that the phase transition point of clauses-to-variables ratio r (dependent on p) can be improved. Moreover, we show that the upper bound of p<jats:sub>c<\/jats:sub> can be reduced to 0.6846. This fact implies that, for a constant \u03bb &lt; 1, a random (2 + p)-SAT formula with \u03bbn 2-clauses and 2.17n 3-clauses is almost surely unsatisfiable. <\/jats:p>","DOI":"10.1142\/s0129054113500251","type":"journal-article","created":{"date-parts":[[2013,12,27]],"date-time":"2013-12-27T08:17:54Z","timestamp":1388132274000},"page":"899-912","source":"Crossref","is-referenced-by-count":1,"title":["A NEW UPPER BOUND FOR RANDOM (2 + <i>p<\/i>)-SAT BY FLIPPING TWO VARIABLES"],"prefix":"10.1142","volume":"24","author":[{"given":"GUANGYAN","family":"ZHOU","sequence":"first","affiliation":[{"name":"LMIB and School of Mathematics and Systems Science, Beihang University, Beijing, 100191, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ZONGSHENG","family":"GAO","sequence":"additional","affiliation":[{"name":"LMIB and School of Mathematics and Systems Science, Beihang University, Beijing, 100191, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,12,27]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.011"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00154-2"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-04-00464-3"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.020"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022885828956"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0081"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<467::AID-RSA15>3.0.CO;2-W"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00049-6"},{"issue":"46","key":"p_17","first-page":"9209","volume":"31","author":"Monasson R.","journal-title":"Gen."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113500251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:10:59Z","timestamp":1565122259000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113500251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":11,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2013,12,27]]},"published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1142\/S0129054113500251"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113500251","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}