{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T09:33:49Z","timestamp":1778751229515,"version":"3.51.4"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T00:00:00Z","timestamp":1466985600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["GRF 616013"],"award-info":[{"award-number":["GRF 616013"]}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP110101042 and DP130102302"],"award-info":[{"award-number":["DP110101042 and DP130102302"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"name":"China National 973 Program and NSFC","award":["2014CB340301 and 61379043"],"award-info":[{"award-number":["2014CB340301 and 61379043"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2016,7,22]]},"abstract":"<jats:p>The critical behaviors of NP-complete problems have been studied extensively, and numerous results have been obtained for Boolean formula satisfiability (SAT) and constraint satisfaction (CSP), among others. However, few results are known for the critical behaviors of NP-hard nonmonotonic reasoning problems so far; in particular, a mathematical model for phase transition in nonmonotonic reasoning is still missing. In this article, we investigate the phase transition of negative two-literal logic programs under the answer-set semantics. We choose this class of logic programs since it is the simplest class for which the consistency problem of deciding if a program has an answer set is still NP-complete. We first introduce a new model, called quadratic model for generating random logic programs in this class. We then mathematically prove that the consistency problem for this class of logic programs exhibits a phase transition. Furthermore, the phase-transition follows an easy-hard-easy pattern. Given the correspondence between answer sets for negative two-literal programs and kernels for graphs, as a corollary, our result significantly generalizes de la Vega's well-known theorem for phase transition on the existence of kernels in random graphs. We also report some experimental results. Given our mathematical results, these experimental results are not really necessary. We include them here as they suggest that our phase-transition result is more general and likely holds for more general classes of logic programs.<\/jats:p>","DOI":"10.1145\/2926791","type":"journal-article","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T15:39:29Z","timestamp":1467041969000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Model for Phase Transition of Random Answer-Set Programs"],"prefix":"10.1145","volume":"17","author":[{"given":"Lian","family":"Wen","sequence":"first","affiliation":[{"name":"Griffith University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kewen","family":"Wang","sequence":"additional","affiliation":[{"name":"Griffith University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi-Dong","family":"Shen","sequence":"additional","affiliation":[{"name":"Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fangzhen","family":"Lin","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Handbook of Satisfiability","author":"Achlioptas D.","unstructured":"D. Achlioptas . 2008. Random satisfiability . In Handbook of Satisfiability . A. Biere, M. Heule, H. Van Maaren, T. Walsh, (Eds.). IOS Press , Amsterdam, The Netherlands, 234--268. D. Achlioptas. 2008. Random satisfiability. In Handbook of Satisfiability. A. Biere, M. Heule, H. Van Maaren, T. Walsh, (Eds.). IOS Press, Amsterdam, The Netherlands, 234--268."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP\u201997)","author":"Achlioptas D.","unstructured":"D. Achlioptas , L. Kirousis , E. Kranakis , D. Krizanc , M. Molloy , and Y. Stamatiou . 1997. Random constraint satisfaction: A more accurate picture . In Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP\u201997) . 107--120. D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, and Y. Stamatiou. 1997. Random constraint satisfaction: A more accurate picture. In Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP\u201997). 107--120."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas A. Naor and Y. Peres. 2005. Rigorous location of phase transitions in hard optimization problems. Nature 435 7043 759--764.  D. Achlioptas A. Naor and Y. Peres. 2005. Rigorous location of phase transitions in hard optimization problems. Nature 435 7043 759--764.","DOI":"10.1038\/nature03602"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"H. Blair F. Dushin D. Jakel D. Rivera and M. Sezgin. 1999. Continuous models of computation for logic programs: Importing continuous mathematics into logic programming\u2019s algorithmic foundations. In The Logic Programming Paradigm. 231--255.  H. Blair F. Dushin D. Jakel D. Rivera and M. Sezgin. 1999. Continuous models of computation for logic programs: Importing continuous mathematics into logic programming\u2019s algorithmic foundations. In The Logic Programming Paradigm. 231--255.","DOI":"10.1007\/978-3-642-60085-2_10"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991)","author":"Cheeseman P.","unstructured":"P. Cheeseman , B. Kanefsky , and W. M. Taylor . 1991. Where the really hard problems are . In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991) . 331--340. P. Cheeseman, B. Kanefsky, and W. M. Taylor. 1991. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI\u201991). 331--340."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90327-E"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00158-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_50"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.001"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 5th International Conference and Symposium of Logic Programming (ICLP\u201988)","author":"Gelfond M.","unstructured":"M. Gelfond and V. Lifschitz . 1988. The stable model semantics for logic programming . In Proceedings of the 5th International Conference and Symposium of Logic Programming (ICLP\u201988) . 1070--1080. M. Gelfond and V. Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium of Logic Programming (ICLP\u201988). 1070--1080."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 11th European Conference on Artificial Intelligence (ECAI 94)","author":"Gent I.","unstructured":"I. Gent and T. Walsh . 1994. The SAT phase transition . In Proceedings of the 11th European Conference on Artificial Intelligence (ECAI 94) . 105--109. I. Gent and T. Walsh. 1994. The SAT phase transition. In Proceedings of the 11th European Conference on Artificial Intelligence (ECAI 94). 105--109."},{"key":"e_1_2_1_12_1","unstructured":"R. Graham D. Knuth and O. Patashnik. 1994. Concrete Mathematics A Foundation for Computer Science (2nd ed.). Addison-Wesley Publishing Company New York NY.   R. Graham D. Knuth and O. Patashnik. 1994. Concrete Mathematics A Foundation for Computer Science (2nd ed.). Addison-Wesley Publishing Company New York NY."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 15th Canadian Conference on Artificial Intelligence. 119--131","author":"Huang G.","unstructured":"G. Huang , X. Jia , C. Liau , and J. You . 2002. Two-literal logic programs and satisfiability representation of stable models: A comparison . In Proceedings of the 15th Canadian Conference on Artificial Intelligence. 119--131 . G. Huang, X. Jia, C. Liau, and J. You. 2002. Two-literal logic programs and satisfiability representation of stable models: A comparison. In Proceedings of the 15th Canadian Conference on Artificial Intelligence. 119--131."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90033-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"e_1_2_1_16_1","unstructured":"M. Karonski and T. Luczak. 1996. Random hypergraphs. In Combinatorics Paul Erdos is Eighty Vol. 2. 283--293.  M. Karonski and T. Luczak. 1996. Random hypergraphs. In Combinatorics Paul Erdos is Eighty Vol. 2. 283--293."},{"key":"e_1_2_1_17_1","first-page":"759","article-title":"Critical behavior in the satisfiability of random Boolean expressions","volume":"264","author":"Kirkpatrick S.","year":"2005","unstructured":"S. Kirkpatrick and B. Selman . 2005 . Critical behavior in the satisfiability of random Boolean expressions . Science 264 , 759 -- 764 . S. Kirkpatrick and B. Selman. 2005. Critical behavior in the satisfiability of random Boolean expressions. Science 264, 759--764.","journal-title":"Science"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840300173X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116836"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/549551"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 10th National Conference on Artificial Intelligence (AAAI\u201992)","author":"Mitchell D.","unstructured":"D. Mitchell , B. Selman , and H. Levesque . 1992. Hard and easy distributions of SAT problems . In Proceedings of the 10th National Conference on Artificial Intelligence (AAAI\u201992) . 459--465. D. Mitchell, B. Selman, and H. Levesque. 1992. Hard and easy distributions of SAT problems. In Proceedings of the 10th National Conference on Artificial Intelligence (AAAI\u201992). 459--465."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4%3C414::AID-RSA10%3E3.0.CO;2-G"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_20"},{"key":"e_1_2_1_25_1","unstructured":"J. Schlipf M. Truszczynski and D. Wong. 2005. On the distribution of programs with stable models. In 05171 Abstracts Collection - Nonmonotonic Reasoning Answer Set Programming and Constraints.  J. Schlipf M. Truszczynski and D. Wong. 2005. On the distribution of programs with stable models. In 05171 Abstracts Collection - Nonmonotonic Reasoning Answer Set Programming and Constraints."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201901)","author":"Syrj\u00e4nen T.","unstructured":"T. Syrj\u00e4nen and I. Niemel\u00e4 . 2001. The smodels system . In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201901) . 434--438. T. Syrj\u00e4nen and I. Niemel\u00e4. 2001. The smodels system. In Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201901). 434--438."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"K. Wang L. Wen and K. Mu. 2015. Random logic programs: Linear model. Theory and Practice of Logic Programming 15.  K. Wang L. Wen and K. Mu. 2015. Random logic programs: Linear model. Theory and Practice of Logic Programming 15.","DOI":"10.1017\/S1471068414000611"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 19th International Conference on Logic Programming (ICLP\u201903)","author":"Zhao Y.","unstructured":"Y. Zhao and F. Lin . 2003. Answer set programming phase transition: A study on randomly generated programs . In Proceedings of the 19th International Conference on Logic Programming (ICLP\u201903) . 239--253. Y. Zhao and F. Lin. 2003. Answer set programming phase transition: A study on randomly generated programs. In Proceedings of the 19th International Conference on Logic Programming (ICLP\u201903). 239--253."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2926791","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2926791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:21Z","timestamp":1750222581000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2926791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,27]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,7,22]]}},"alternative-id":["10.1145\/2926791"],"URL":"https:\/\/doi.org\/10.1145\/2926791","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,27]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}