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.