The complexity of inferences and explanations in probabilistic logic programming. (English) Zbl 1491.68041

Antonucci, Alessandro (ed.) et al., Symbolic and quantitative approaches to reasoning with uncertainty. 14th European conference, ECSQARU 2017, Lugano, Switzerland, July 10–14, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10369, 449-458 (2017).
Summary: A popular family of probabilistic logic programming languages combines logic programs with independent probabilistic facts. We study the complexity of marginal inference, most probable explanations, and maximum a posteriori calculations for propositional/relational probabilistic logic programs that are acyclic/definite/stratified/normal/ disjunctive. We show that complexity classes \(\varSigma_k\) and \(\mathsf {PP}^{\varSigma_k}\) (for various values of \(k\)) and \(\mathsf {NP}^\mathsf {PP}\) are all reached by such computations.
For the entire collection see [Zbl 1367.68004].


68N17 Logic programming
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68T37 Reasoning under uncertainty in the context of artificial intelligence
Full Text: DOI