{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T02:07:41Z","timestamp":1784858861730,"version":"3.55.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,2]],"date-time":"2015-06-02T00:00:00Z","timestamp":1433203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"project PON01&lowbar;01286 - eJRM (electronic Justice Relationship Management)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2015,7,8]]},"abstract":"<jats:p>Probabilistic abstract argumentation combines Dung\u2019s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that a set of arguments is an<jats:italic>extension<\/jats:italic>according to a given semantics. We focus on the most popular semantics (i.e.,<jats:italic>admissible<\/jats:italic>,<jats:italic>stable<\/jats:italic>,<jats:italic>complete<\/jats:italic>,<jats:italic>grounded<\/jats:italic>,<jats:italic>preferred<\/jats:italic>,<jats:italic>ideal-set<\/jats:italic>,<jats:italic>ideal<\/jats:italic>,<jats:italic>stage<\/jats:italic>, and<jats:italic>semistable<\/jats:italic>) and show the following dichotomy result: computing the probability that a set of arguments is an extension is either<jats:italic>FP<\/jats:italic>or<jats:italic>FP<\/jats:italic><jats:sup>#<jats:italic>P<\/jats:italic><\/jats:sup>-complete depending on the semantics adopted. Our polynomial-time results are particularly interesting, as they hold for some semantics for which no polynomial-time technique was known so far.<\/jats:p>","DOI":"10.1145\/2749463","type":"journal-article","created":{"date-parts":[[2015,6,2]],"date-time":"2015-06-02T18:19:47Z","timestamp":1433269187000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["On the Complexity of Probabilistic Abstract Argumentation Frameworks"],"prefix":"10.1145","volume":"16","author":[{"given":"Bettina","family":"Fazzinga","sequence":"first","affiliation":[{"name":"ICAR-CNR, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergio","family":"Flesca","sequence":"additional","affiliation":[{"name":"DIMES - University of Calabria, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Parisi","sequence":"additional","affiliation":[{"name":"DIMES - University of Calabria, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,6,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2007.07.004"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.fss.2007.12.013"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014490210693"},{"key":"e_1_2_1_4_1","unstructured":"Leila Amgoud and Henri Prade. 2004. Reaching agreement through argumentation: A possibilistic approach. In Principles of Knowledge Representation and Reasoning (KR). 175--182. Leila Amgoud and Henri Prade. 2004. Reaching agreement through argumentation: A possibilistic approach. In Principles of Knowledge Representation and Reasoning (KR). 175--182."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-011-9271-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888911000166"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Pietro Baroni and Massimiliano Giacomin. 2009. Semantics of abstract argument systems. In Argumentation in Artificial Intelligence. 25--44. Pietro Baroni and Massimiliano Giacomin. 2009. Semantics of abstract argument systems. In Argumentation in Artificial Intelligence. 25--44.","DOI":"10.1007\/978-0-387-98197-0_2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2005.05.006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.3.429"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.05.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Philippe Besnard and Anthony Hunter (Eds.). 2008. Elements of Argumentation. MIT Press. Philippe Besnard and Anthony Hunter (Eds.). 2008. Elements of Argumentation. MIT Press.","DOI":"10.7551\/mitpress\/9780262026437.001.0001"},{"key":"e_1_2_1_12_1","unstructured":"Martin Caminada. 2006. Semi-stable semantics. In Computational Models of Argument (COMMA). 121--130. Martin Caminada. 2006. Semi-stable semantics. In Computational Models of Argument (COMMA). 121--130."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exr033"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1105924.1106116"},{"key":"e_1_2_1_15_1","unstructured":"Sylvie Coste-Marquis S\u00e9bastien Konieczny Pierre Marquis and Mohand Akli Ouali. 2012. Weighted attacks in argumentation frameworks. In Principles of Knowledge Representation and Reasoning (KR). 593--597. Sylvie Coste-Marquis S\u00e9bastien Konieczny Pierre Marquis and Mohand Akli Ouali. 2012. Weighted attacks in argumentation frameworks. In Principles of Knowledge Representation and Reasoning (KR). 593--597."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"P. M. Dung R. A. Kowalski and F. Toni. 2009. Assumption-based argumentation. In Argumentation in Artificial Intelligence. 199--218. P. M. Dung R. A. Kowalski and F. Toni. 2009. Assumption-based argumentation. In Argumentation in Artificial Intelligence. 199--218.","DOI":"10.1007\/978-0-387-98197-0_10"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00041-X"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.05.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Phan Minh Dung and Phan Minh Thang. 2010. Towards (probabilistic) argumentation for jury-based dispute resolution. In Computational Models of Argument (COMMA). 171--182. Phan Minh Dung and Phan Minh Thang. 2010. Towards (probabilistic) argumentation for jury-based dispute resolution. In Computational Models of Argument (COMMA). 171--182.","DOI":"10.3233\/978-1-60750-619-5-171"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2009.09.001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.09.005"},{"key":"e_1_2_1_22_1","volume-title":"Dunne and Michael Wooldridge","author":"Paul","year":"2009","unstructured":"Paul E. Dunne and Michael Wooldridge . 2009 . Complexity of abstract argumentation. In Argumentation in Artificial Intelligence . 85--104. Paul E. Dunne and Michael Wooldridge. 2009. Complexity of abstract argumentation. In Argumentation in Artificial Intelligence. 85--104."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.10.001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.04.005"},{"key":"e_1_2_1_26_1","volume-title":"Fundamentals of Computation Theory, Bogdan S","author":"Eiter Thomas","unstructured":"Thomas Eiter and Georg Gottlob . 1997. The complexity class &Theta;p2 : Recent results and applications in AI and modal logic . In Fundamentals of Computation Theory, Bogdan S . Chlebus and Ludwik Czaja (Eds.). Lecture Notes in Computer Science, Vol. 1279 . Springer , Berlin, 1--18. Thomas Eiter and Georg Gottlob. 1997. The complexity class &Theta;p2 : Recent results and applications in AI and modal logic. In Fundamentals of Computation Theory, Bogdan S. Chlebus and Ludwik Czaja (Eds.). Lecture Notes in Computer Science, Vol. 1279. Springer, Berlin, 1--18."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40381-1_9"},{"key":"e_1_2_1_28_1","volume-title":"International Joint Conference on Artificial Intelligence (IJCAI). 898--904","author":"Fazzinga Bettina","year":"2013","unstructured":"Bettina Fazzinga , Sergio Flesca , and Francesco Parisi . 2013 b. On the complexity of probabilistic abstract argumentation . In International Joint Conference on Artificial Intelligence (IJCAI). 898--904 . Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. 2013b. On the complexity of probabilistic abstract argumentation. In International Joint Conference on Artificial Intelligence (IJCAI). 898--904."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11591191_34"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.04.026"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exs011"},{"key":"e_1_2_1_32_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & amp; Co. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co."},{"key":"e_1_2_1_33_1","volume-title":"International Joint Conference on Artificial Intelligence (IJCAI). 143--149","author":"Grossi Davide","unstructured":"Davide Grossi and Wiebe van der Hoek. 2013. Audience-based uncertainty in abstract argument games . In International Joint Conference on Artificial Intelligence (IJCAI). 143--149 . Davide Grossi and Wiebe van der Hoek. 2013. Audience-based uncertainty in abstract argument games. In International Joint Conference on Artificial Intelligence (IJCAI). 143--149."},{"key":"e_1_2_1_34_1","volume-title":"ECSQARU Workshop: Adventures in Argumentation. 19--25","author":"Haenni R.","unstructured":"R. Haenni , B. Anrig , J. Kohlas , and N. Lehmann . 2001. A survey on probabilistic argumentation . In ECSQARU Workshop: Adventures in Argumentation. 19--25 . R. Haenni, B. Anrig, J. Kohlas, and N. Lehmann. 2001. A survey on probabilistic argumentation. In ECSQARU Workshop: Adventures in Argumentation. 19--25."},{"key":"e_1_2_1_35_1","volume-title":"Algorithms for Uncertainty and Defeasible Reasoning","author":"Haenni R.","year":"2000","unstructured":"R. Haenni , J. Kohlas , and N. Lehmann . 2000 . Probabilistic argumentation systems. In Handbook of Defeasible Reasoning and Uncertainty Management Systems , Volume 5 : Algorithms for Uncertainty and Defeasible Reasoning . Kluwer , 221--288. R. Haenni, J. Kohlas, and N. Lehmann. 2000. Probabilistic argumentation systems. In Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning. Kluwer, 221--288."},{"key":"e_1_2_1_36_1","unstructured":"Anthony Hunter. 2012. Some foundations for probabilistic abstract argumentation. In Computational Models of Argument (COMMA). 117--128. Anthony Hunter. 2012. Some foundations for probabilistic abstract argumentation. In Computational Models of Argument (COMMA). 117--128."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40381-1_5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2012.08.003"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2013.09.002"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9392-5"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.001"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29184-5_1"},{"key":"e_1_2_1_43_1","volume-title":"Workshop on Argumentation in Multi-Agent Systems (ArgMAS).","author":"Li Hengfei","unstructured":"Hengfei Li , Nir Oren , and Timothy J. Norman . 2013. Relaxing independence assumptions in probabilistic argumentation . In Workshop on Argumentation in Multi-Agent Systems (ArgMAS). Hengfei Li, Nir Oren, and Timothy J. Norman. 2013. Relaxing independence assumptions in probabilistic argumentation. In Workshop on Argumentation in Multi-Agent Systems (ArgMAS)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622859.1622866"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/377978.377983"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2006.06.012"},{"key":"e_1_2_1_47_1","volume-title":"Alejandro Javier Garc\u00eda, and Guillermo Ricardo Simari","author":"Mart\u00ednez Diego C.","year":"2008","unstructured":"Diego C. Mart\u00ednez , Alejandro Javier Garc\u00eda, and Guillermo Ricardo Simari . 2008 . An abstract argumentation framework with varied-strength attacks. In Principles of Knowledge Representation and Reasoning (KR) . 135--144. Diego C. Mart\u00ednez, Alejandro Javier Garc\u00eda, and Guillermo Ricardo Simari. 2008. An abstract argumentation framework with varied-strength attacks. In Principles of Knowledge Representation and Reasoning (KR). 135--144."},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"C. Meinel and T. Theobald. 1998. Algorithms and Data Structures in VLSI Design. Springer-Verlag. C. Meinel and T. Theobald. 1998. Algorithms and Data Structures in VLSI Design. Springer-Verlag.","DOI":"10.1007\/978-3-642-58940-9"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2009.02.001"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90061-J"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2362076.2362080"},{"key":"e_1_2_1_52_1","unstructured":"Nir Oren and Timothy J. Norman. 2008. Semantics for evidence-based argumentation. In Computational Models of Argument (COMMA). 276--284. Nir Oren and Timothy J. Norman. 2008. Semantics for evidence-based argumentation. In Computational Models of Argument (COMMA). 276--284."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05258-3_2"},{"key":"e_1_2_1_54_1","volume-title":"Computational Complexity","author":"Papadimitriou C. M.","unstructured":"C. M. Papadimitriou . 1994. Computational Complexity . Addison-Wesley . C. M. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00027-1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1080\/19462160903564592"},{"key":"e_1_2_1_57_1","unstructured":"Iyad Rahwan and Guillermo R. Simari (Eds.). 2009. Argumentation in Artificial Intelligence. Springer. Iyad Rahwan and Guillermo R. Simari (Eds.). 2009. Argumentation in Artificial Intelligence. Springer."},{"key":"e_1_2_1_58_1","volume-title":"International Conference on Agreement Technologies (AT). 138--152","author":"Rienstra Tjitze","year":"2012","unstructured":"Tjitze Rienstra . 2012 . Towards a probabilistic dung-style argumentation system . In International Conference on Agreement Technologies (AT). 138--152 . Tjitze Rienstra. 2012. Towards a probabilistic dung-style argumentation system. In International Conference on Agreement Technologies (AT). 138--152."},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan &amp; Claypool. Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan &amp; Claypool.","DOI":"10.1007\/978-3-031-01879-4"},{"key":"e_1_2_1_60_1","volume-title":"European Conference on Artificial Intelligence (ECAI). 750--755","author":"Thimm Matthias","year":"2012","unstructured":"Matthias Thimm . 2012 . A probabilistic semantics for abstract argumentation . In European Conference on Artificial Intelligence (ECAI). 750--755 . Matthias Thimm. 2012. A probabilistic semantics for abstract argumentation. In European Conference on Artificial Intelligence (ECAI). 750--755."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90369-Q"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_63_1","volume-title":"International Conference on Formal and Applied Practical Reasoning Workshop (FAPR). 357--368","author":"Verheij Bart","year":"1996","unstructured":"Bart Verheij . 1996 . Two approaches to dialectical argumentation: Admissible sets and argumentation stages . In International Conference on Formal and Applied Practical Reasoning Workshop (FAPR). 357--368 . Bart Verheij. 1996. Two approaches to dialectical argumentation: Admissible sets and argumentation stages. In International Conference on Formal and Applied Practical Reasoning Workshop (FAPR). 357--368."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2749463","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2749463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:04Z","timestamp":1750273444000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2749463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,2]]},"references-count":62,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7,8]]}},"alternative-id":["10.1145\/2749463"],"URL":"https:\/\/doi.org\/10.1145\/2749463","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,2]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}