A First Journey into the Complexity of Statistical Statements in Probabilistic Answer Set Programming

Probabilistic Answer Set Programming is an efficient formalism to express uncertain information with an answer set program (PASP). Recently, this formalism has been extended with statistical statements, i.e., statements that can encode a certain property of the considered domain, within the PASTA framework. To perform inference, these statements are converted into answer set rules and constraints with aggregates. The complexity of PASP has been studied in depth, with results regarding both membership and completeness. However, a complexity analysis of programs with statements is missing. In this paper, we close this gap by studying the complexity of PASTA statements.