# Complexity results for probabilistic answer set programming

Denis Deratani Mauá, Fabio Gagliardi Cozman

January 2020
### Abstract

We analyze the computational complexity of probabilistic logic programming with constraints, disjunctive heads, and aggregates such as sum and max. We consider propositional programs and relational programs with bounded-arity predicates, and look at cautious reasoning (i.e., computing the smallest probability of an atom over all probability models), cautious explanation (i.e., finding an interpretation that maximizes the lower probability of evidence) and cautious maximum-a-posteriori (i.e., finding a partial interpretation for a set of atoms that maximizes their lower probability conditional on evidence) under Lukasiewicz’s credal semantics.

Publication

*International Journal of Approximate Reasoning*