Reasoning with Restricted Statistical Statements in Probabilistic Answer Set Programming: Complexity and Algorithms

Statistical statements are an expressive tool for representing statistical information of a domain of interest. Recently, these statements were given a meaning in the context of Probabilistic Answer Set Programming (PASP), allowing one to encode properties like "x% of elements of a domain have the feature y". Although the computational complexity of different tasks in PASP is well known, the complexity of restricted programs composed only of statistical statements and probabilistic facts has not been studied. As a first contribution, we address this problem, confirming that even in seemingly restricted cases the complexity is high. Indeed, even with this restriction we do not lose expressiveness, reaching higher levels of the polynomial hierarchy. To mitigate these high complexities, we focus on the structure of the programs. Thereby, we design novel structure-guided reductions, demonstrating how one can efficiently answer queries along treewidth decompositions. We obtain precise upper bounds and we show that under reasonable assumptions in complexity theory we cannot significantly improve, as we give matching lower bounds.