Probabilistic Answer Set Programming is an eficient 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.
Representing uncertain information with an interpretable language is currently one of the main goal of
Statistical Relational Artificial Intelligence [
More than 30 years ago, Halpern [
Inference in PASP has been proved hard [
In this paper, we focus on PASP composed by a set of probabilistic facts and a set of statistical statements only, and we study the complexity of inference in such programs. Theoretical results show that, in such simple programs, inference can be eficiently computed.
The paper is structured as follows: Section 2 discusses some background knowledge related to Answer Set Programming, Probabilistic Answer Set Programming and statistical statements, and Computational Complexity. In Section 3 we study the complexity of programs with statistical statements. Section 4 surveys related work and Section 5 concludes the paper.
Answer Set Programming [
We consider the Stable Model Semantics [16] as semantics for answer set programs. Under this semantics, each program is associated with zero (in this case the program is often termed unsatisfiable ) or more stable models. A program is called ground when there are no variables in it. A non ground program can be transformed into a ground program with a process called grounding. The Herbrand base of a ground program is the set of all possible ground atoms that can be constructed using the symbols defined in , often indicated with . An interpretation is a subset of . The reduct of a ground program w.r.t. a subset of (this subset is called interpretation), denoted with , is computed by removing from the rules having at least one literal in the body is false in . An interpretation is called stable model or answer set of a program if it is a minimal model under set inclusion of . We use ( ) to denote the set of answer sets of . Let us clarify these definitions with an example. Example 1. The following answer set program has two facts and three rules. qa:- a. qb:- b, not nqb. nqb:- b, not qb.
It has two answer sets: {, , , } and {, , , }.
To describe uncertain scenarios with Answer Set Programming, several semantics have been proposed,
such as LPMLN [17], P-log [18], and the credal semantics [
Π :: .
where Π ∈]0, 1[ and is an atom. Intuitively, Π is the probability that is included in the program
and 1 − Π that it is excluded. In the remaining part of the paper, we use the acronym PASP to indicate
both Probabilistic Answer Set Programming under the credal semantics and a probabilistic answer set
program interpreted under the credal semantics. Each PASP with probabilistic fact defines 2 world,
obtained by considering each possible selection of probabilistic facts. Let us call the set of all the
worlds. The probability of a world ∈ is computed as [
∈ ̸∈ that is, by considering the probabilistic facts present or absent in . In each world the set of probabilistic facts is fixed, so each world is an answer set program. Thus, may have 0 more answer sets but the credal semantics requires that it has at least one. In this paper, we will always assume that every PASP has at least one answer set per world. Given a conjunction of ground literals , often called query, its probability () is described by a range [P(), P()] whose bounds depend on the number of answer sets of every world with the query included. A world contributes to both the lower (P()) and upper (P()) bound for a query if is present in every answer set. Otherwise, if the query is true only in some answer sets, contributes only to the upper probability bound. If the query is present in none of the answer sets of , contributes to none of the bounds. In formulas, () = [P(), P()] = [ ∑︁ (), ∑︁ ()] ∈ .. ∀∈(), |= ∈ .. ∃∈(), |=
Example 2. The following program has two probabilistic facts, and . 0.4::a. 0.3::b. qa:- a. qb:- b, not nqb. nqb:- b, not qb. q:- qa. q:- qb.
It has 22 = 4 worlds: 0, where neither nor are present, whose probability is (1 − 0.4) · (1 − 0.3) = 0.6 · 0.7 = 0.42 and (0) = {{}}; 1, where is present and is absent, whose probability is 0.4 · (1 − 0.3) = 0.4 · 0.7 = 0.28 and (1) = {{, , }}; 2, where is absent and is present, whose probability is (1 − 0.4) · 0.3 = 0.6 · 0.3 = 0.18 and (2) = {{, , }, {, }}; and 3, where both and are present, whose probability is 0.4 · 0.3 = 0.4 · 0.3 = 0.12 and (3) = {{, , , , }, {, , , , }}. If we are interested in computing the probability of , we have that 0 contributes to none of the bounds since is present in none of its answer sets, 1 contributes to both the lower and upper bound since is present in every answer set (there is only one with in it), 2 contributes to only the upper bound since is present in only one of the two answer sets, and 3 contributes to both the lower and upper bound since is present in every answer set (both have in it). Overall, [P(), P()] = [ (1) + (3), (1) + (2) + (3)] = [0.28 + 0.12, 0.28 + 0.18 + 0.12] = [0.4, 0.58].
Halpern’s statistical statements [
Example 3 (from [
The probabilistic facts indicate that the animals indexed with 1 up to 4 are birds with a probability of 0.4. The statement describes that at least 60% of the birds fly (and at most 100%, all of them). To perform inference, this program is converted into; 0.4::bird(1). 0.4::bird(2). 0.4::bird(3). fly(X) ; not_fly(X) :- bird(X). :- #count{X:fly(X),bird(X)} = FB, #count{X:bird(X)} = B, 10*FB < 6*B.
If we want to compute the probability of the query fly(1), we get 0.336 for the lower and 0.4 for the upper probability.
We can convert the program above into a program without counting aggregates, by enumerating all the possible results of the aggregates. For examples, the program shown in Example 3 can be converted into:
We assume familiarity with computational complexity and use complexity classes as usual, see, e.g., [20,
21]. In particular, we use the complexity class PP for probabilistic polynomial-time problems [22] and
we rely on oracle notations as usual. A complete canonical problem for PP is to decide whether a
propositional formula has at least ∈ N satisfying assignments. More formally, the goal is to evaluate
whether the formula = #≥ . () evaluates to true, where () is a 3-CNF formula over variables
in . This is the case if there are at least satisfying assignments of . Analogously, evaluating formulas
of the form = #≥ .∀. (, ) with being a Boolean formula in 3-DNF over variables in ∪ , is
PPNP-complete. Intuitively, this requires witnessing at least assignments over , where any extension
of these assignments over variables , ensures that evaluates to true. For a detailed introduction over
this formalism and a survey on complexity results for probabilistic reasoning, see [
We obtain the following complexity results, which underline the simplicity of inference for PASTA
programs. As in [
Theorem 1 (Complexity). Inference in PASTA programs under credal semantics is PPNP-complete. Proof. Hardness: We reduce from #≥ .∀. (, ) with being a Boolean formula in 3-DNF over variables in = {1, . . . , } and = {1, . . . , }. We construct a PASTA program Π , where for every variable occurring in , we add probabilistic facts
We care about satisfied worlds, so we guess the state of satisfiability for every DNF term sat() ; nsat().
sat ; nsat.
We guess the truth assignments for every universally quantified variable ∈ : For every DNF term , every positive variable in and every negative occurrence ¬ add:
:- #count {C : sat(C)}=T, #count {1: sat}=S, T<S. :- #count {C : nsat(C)}=T, #count {1: nsat}=S, S*| | >T.
:- #count {V : t(V), pos(,V); V : not t(V), neg(,V)}=T, #count {1 : sat()}=S, T<3S.
:- #count {V : t(V), pos(,V); V : not t(V), neg(,V)}=T,
#count {1 : nsat()}=S, T=3S.
It is easy to see that #≥ {1, . . . , }. holds, i.e., there are at least satisfying assignments of if and only if P({}) ≥ 2 .
Note that since is in 3-CNF, all constraint sizes are constant. Indeed, the aggregate body sizes are at most 3 and we could even slightly adapt the proof to only use ground rules (i.e., without first-order variables).
Membership: Follows directly from previous work [10, Table 1], which shows PPNP membership for aggregates and default negation. Indeed, disjunction in PASTA programs can be directly translated to default negation [23], as by definition there can not be a cyclic dependency between disjunctive head atoms.
Note that disjunction or, alternatively, default negation is crucial in PASTA programs. Indeed, if we did not allow disjunction, such programs can only capture co-NP decision complexity. Theorem 2 (Complexity without disjunction). Inference in PASTA programs under credal semantics without disjunctions is co-NP-complete.
Proof. Hardness: We reduce from ∀. (), where () is in 3-DNF over variables in = {1, . . . , }. We construct a PASTA program Π , where for every variable occurring in , we add probabilistic facts
For every 3-DNF term we assume an arbitrary but fixed order among its literals 1 ∧ 2 ∧ 3. Then, for the -th variable such that = (positive occurrence in ) and for the -th variable such that = ¬, we add the facts: pos(, ). neg(, ). sat.
For every 3-DNF term , we add the following constraint which counts all satisfied 3-DNF terms (going over all valid 23 cases): :- #count {
C: t(V1), t(V2), t(V3), pos1(,V1), pos2(,V2), pos3(,V3); C: not t(V1), t(V2), t(V3), neg1(,V1), pos2(,V2), pos3(,V3); C: t(V1), not t(V2), t(V3), pos1(,V1), neg2(,V2), pos3(,V3); C: t(V1), t(V2), not t(V3), pos1(,V1), pos2(,V2), neg3(,V3); C: not t(V1), not t(V2), t(V3), neg1(,V1), neg2(,V2), pos3(,V3); C: not t(V1), t(V2), not t(V3), neg1(,V1), pos2(,V2), neg3(,V3); C: t(V1), not t(V2), not t(V3), pos1(,V1), neg2(,V2), neg3(,V3); C: not t(V1), not t(V2), not t(V3), neg1(,V1), neg2(,V2), neg3(,V3) }=T, #count {1 : sat}=S, T<S.
By the credal semantics, a query can only be answered positively, if there is no world without any answer set. Consequently, we have that ∀. () evaluates to true if and only if P({}) ≥ 1.
Membership: In order to answer a query P( | ) ≥ for a given PASTA program Π , we need to ensure that there is no world without an answer set. This is the co-problem of finding some world without an answer set. In order to find such a world, we just guess any subset of facts and check in polynomial time whether the guess fulfills all aggregate constraints. Observe that for the guess the query P( | ) ≥ can then be answered in polynomial time. Indeed, we do so by using the P(∩) known relationship [10, Eqs (4)] P( | ) = P(∩)+P(∩) . It is easy to see that thereby P() can be computed by just multiplying probabilities of the literals in . Consequently, we can answer P( | ) ≥ in polynomial time (without the need to go over the potentially exponential number of worlds individually). Analogously this works for answering queries of the form P( | ) ≥ instead of P( | ) ≥ , as we have P( | ) = P( | ).
Diferent semantics have been proposed in Probabilistic Answer Set Programming. Here we focused on
the credal semantics. However, there are alternatives such as LPMLN [24], P-log [18], smProbLog [25],
and PrASP [26]. As discussed through the paper, the complexity of PASP under the credal semantics has
been studied in depth in [
In this paper, we provided an initial study of the complexity of the statistical statements provided by the PASTA framework. These statements are represented with a probabilistic answer set program, interpreted under the credal semantics, by means of disjunctive rules and constraints with counting aggregates involved. Our results show that PASTA programs are quite rich, as we reach PPNP-completeness. However, the hardness proof of this result in Theorem 1 relies on using disjunction (or, alternatively, cyclic default negation), so without this language feature we can only reach co-NP completeness, as shown in Theorem 2. As a future work we plan to extend the complexity analysis to also consider the structure of PASTA programs. Artificial Intelligence, volume 14318 of Lecture Notes in Artificial Intelligence , Springer, Heidelberg, Germany, 2023, pp. 367–380. doi:10.1007/978-3-031-47546-7_25. [15] M. Alviano, W. Faber, Aggregates in answer set programming, KI-Künstliche Intelligenz 32 (2018) 119–124. doi:10.1007/s13218-018-0545-9. [16] M. Gelfond, V. Lifschitz, The stable model semantics for logic programming., in: 5th International Conference and Symposium on Logic Programming (ICLP/SLP 1988), volume 88, MIT Press, USA, 1988, pp. 1070–1080. [17] J. Lee, Y. Wang, Weighted rules under the stable model semantics, in: C. Baral, J. P. Delgrande, F. Wolter (Eds.), Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, AAAI Press, 2016, pp. 145–154. [18] C. Baral, M. Gelfond, N. Rushton, Probabilistic reasoning with answer sets, Theory and Practice of Logic Programming 9 (2009) 57–144. doi:10.1017/S1471068408003645. [19] D. Azzolini, F. Riguzzi, Lifted inference for statistical statements in probabilistic answer set programming, International Journal of Approximate Reasoning 163 (2023) 109040. doi:10.1016/ j.ijar.2023.109040. [20] R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, in: 7th Symposia in Applied Mathematics (SIAM 1974), 1974. [21] C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. [22] J. Gill, Computational Complexity of Probabilistic Turing Machines, SIAM J. Comput. 6 (1977) 675–695. URL: https://doi.org/10.1137/0206049. doi:10.1137/0206049. [23] T. Eiter, G. Gottlob, Expressiveness of stable model semantics for disjunctive logic programs with functions, The Journal of Logic Programming 33 (1997) 167–178. [24] J. Lee, Z. Yang, LPMLN, weak constraints, and P-log, in: S. Singh, S. Markovitch (Eds.), Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, AAAI Press, 2017, pp. 1170–1177. [25] P. Totis, L. De Raedt, A. Kimmig, smProbLog: Stable model semantics in ProbLog for probabilistic argumentation, Theory and Practice of Logic Programming (2023) 1–50. doi:10.1017/ S147106842300008X. [26] M. Nickles, A tool for probabilistic reasoning based on logic programming and first-order theories under stable model semantics, in: L. Michael, A. Kakas (Eds.), Logics in Artificial Intelligence, Springer International Publishing, Cham, 2016, pp. 369–384. doi:doi.org/10.1007/ 978-3-319-48758-8_24. [27] M. Jaeger, Probabilistic reasoning in terminological logics, in: J. Doyle, E. Sandewall, P. Torasso (Eds.), 4th International Conference on Principles of Knowledge Representation and Reasoning, Morgan Kaufmann, 1994, pp. 305–316. doi:10.1016/B978-1-4832-1452-8.50124-X.