{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:45:26Z","timestamp":1723016726730},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>We study formal languages which are capable of fully expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects, from a computational complexity perspective.\n\nWe focus on satisfiability problems whose instance formulas allow expressing many tasks in probabilistic and causal inference.\n\nThe main contribution of this work is establishing the exact computational complexity of these satisfiability problems.\n\nWe introduce a new natural complexity class, named succ\u2203R, which can be viewed as a succinct variant of the well-studied class \u2203R, and show that these problems are complete for succ\u2203R.\n\nOur results imply even stronger limitations on the use of algorithmic methods for reasoning about probabilities and causality than  previous state-of-the-art results that rely only on the NP- or \u2203R-completeness of the satisfiability problems for some restricted languages.<\/jats:p>","DOI":"10.24963\/ijcai.2023\/636","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"5730-5738","source":"Crossref","is-referenced-by-count":0,"title":["The Hardness of Reasoning about Probabilities and Causality"],"prefix":"10.24963","author":[{"given":"Benito","family":"van der Zander","sequence":"first","affiliation":[{"name":"Universit\u00e4t zu L\u00fcbeck"}]},{"given":"Markus","family":"Bl\u00e4ser","sequence":"additional","affiliation":[{"name":"Saarland University"}]},{"given":"Maciej","family":"Li\u015bkiewicz","sequence":"additional","affiliation":[{"name":"Universit\u00e4t zu L\u00fcbeck"}]}],"member":"10584","event":{"number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2023","name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","start":{"date-parts":[[2023,8,19]]},"theme":"Artificial Intelligence","location":"Macau, SAR China","end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:52:46Z","timestamp":1691743966000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/636"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/636","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}