{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:01Z","timestamp":1750308541856,"version":"3.41.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319596044"},{"type":"electronic","value":"9783319596051"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59605-1_24","type":"book-chapter","created":{"date-parts":[[2017,5,22]],"date-time":"2017-05-22T15:06:26Z","timestamp":1495465586000},"page":"267-279","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Phase Transition for Maximum Not-All-Equal Satisfiability"],"prefix":"10.1007","author":[{"given":"Junping","family":"Zhou","sequence":"first","affiliation":[]},{"given":"Shuli","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Tingting","family":"Zou","sequence":"additional","affiliation":[]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,23]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/BF02917402","volume":"42","author":"K Xu","year":"1999","unstructured":"Xu, K., Li, W.: The SAT phase transition. Sci. China Ser. E 42, 494\u2013501 (1999)","journal-title":"Sci. China Ser. E"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"Sly, A., Sun, N., Zhang, Y.: The number of solutions for random regular NAE-SAT. In: FOCS (2016)","DOI":"10.1109\/FOCS.2016.82"},{"issue":"2\u20133","key":"24_CR3","first-page":"204","volume":"172","author":"J Larrosa","year":"2006","unstructured":"Larrosa, J., Heras, F., De Givry, S.: A logical approach to efficient Max-SAT solving. Artif. Intell. 172(2\u20133), 204\u2013233 (2006)","journal-title":"Artif. Intell."},{"key":"24_CR4","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 phase transitions. Nature 400, 133\u2013137 (1999)","journal-title":"Nature"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S Kirkpatrick","year":"1994","unstructured":"Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random boolean expressions. Science 264, 1297\u20131301 (1994)","journal-title":"Science"},{"key":"24_CR6","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K Xu","year":"2000","unstructured":"Xu, K., Li, W.: Exact phase transitions in random constraint satisfaction problems. J. Artif. Intell. Res. 12, 93\u2013103 (2000)","journal-title":"J. Artif. Intell. Res."},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2012.08.003","volume":"193","author":"Y Fan","year":"2012","unstructured":"Fan, Y., Shen, J., Xu, K.: A general model and thresholds for random constraint satisfaction problems original. Artif. Intell. 193, 1\u201317 (2012)","journal-title":"Artif. Intell."},{"issue":"1\u20132","key":"24_CR8","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/S0004-3702(96)00030-6","volume":"88","author":"IP Gent","year":"1996","unstructured":"Gent, I.P., Walsh, T.: The TSP phase transition. Artif. Intell. 88(1\u20132), 349\u2013358 (1996)","journal-title":"Artif. Intell."},{"key":"24_CR9","unstructured":"Walsh, T.: Where are the really hard manipulation problems? the phase transition in manipulating the veto rule. In: Proceedings of the 21st International Jont Conference on Artifical intelligence, Morgan Kaufmann Publishers Inc. (2009)"},{"issue":"7","key":"24_CR10","first-page":"1","volume":"57","author":"P Huang","year":"2014","unstructured":"Huang, P., Yin, M.: An upper (lower) bound for Max (Min) CSP. Sci. China Inf. Sci. 57(7), 1\u20139 (2014)","journal-title":"Sci. China Inf. Sci."},{"key":"24_CR11","first-page":"1","volume":"58","author":"J Gao","year":"2015","unstructured":"Gao, J., Wang, J., Yin, M.: Experimental analyses on phase transitions in compiling satisfiability problems. Sci. China Inf. Sci. 58, 1\u201311 (2015)","journal-title":"Sci. China Inf. Sci."},{"issue":"01","key":"24_CR12","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1142\/S0129054112500025","volume":"23","author":"J Zhou","year":"2012","unstructured":"Zhou, J., Yin, M., Li, X., Wang, J.: Phase transitions of EXPSPACE-complete problems: a further step. Int. J. Found. Comput. Sci. 23(01), 173\u2013184 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"24_CR13","unstructured":"Achlioptas, D., Chtcherba, A., Istrate, G., Moore, C.: The phase transition in 1-in-k SAT and NAE 3-SAT. In: SODA, pp. 721\u2013722 (2001)"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Achlioptas, D.: The asymptotic order of the random k-SAT threshold. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS02), pp. 779\u2013788 (2002)","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Coja-Oglan, A., Panagiotou, K.: Catching the k-NAE SAT threshold. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 899\u2013908 (May 2012)","DOI":"10.1145\/2213977.2214058"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Ding, J., Sly, A., Sun, N.: Satisfiability threshold for random regular NAE-SAT. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 814\u2013822 (May 2014)","DOI":"10.1145\/2591796.2591862"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1038\/nature03602","volume":"435","author":"D Achlioptas","year":"2005","unstructured":"Achlioptas, D., Naor, A., Peres, Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759\u2013764 (2005)","journal-title":"Nature"},{"key":"24_CR18","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1002\/rsa.20015","volume":"24","author":"D Coppersmith","year":"2004","unstructured":"Coppersmith, D., et al.: Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Algorithms 24, 502\u2013545 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.ipl.2010.11.002","volume":"111","author":"XL Xu","year":"2011","unstructured":"Xu, X.L., Gao, Z.S., Xu, K.: A tighter upper bound for random MAX 2-SAT. Inf. Process. Lett. 111, 115\u2013119 (2011)","journal-title":"Inf. Process. Lett."},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/3-540-45578-7_11","volume-title":"Principles and Practice of Constraint Programming \u2014 CP 2001","author":"W Zhang","year":"2001","unstructured":"Zhang, W.: Phase transitions and backbones of 3-SAT and maximum 3-SAT. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 153\u2013167. Springer, Heidelberg (2001). doi:10.1007\/3-540-45578-7_11"},{"key":"24_CR21","unstructured":"Bailey, D.D., Kolaitis, P.G.: Phase transitions of bounded satisfiability problems. In: IJCAI, pp. 1187\u20131193 (2003)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59605-1_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:56:26Z","timestamp":1750272986000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-59605-1_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319596044","9783319596051"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59605-1_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"23 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"faw2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/faw2017.uestc.edu.cn","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}