Introduction

Representing uncertain information with an interpretable language is currently one of the main goal of Statistical Relational Artificial Intelligence [1]. Among the different languages, we have ProbLog [2], Logic Programs with Annotated Disjunctions [3], and Stochastic Logic Programs [4] while some of the possible semantics are the Distribution Semantics [5] and the Credal Semantics [6]. Answer Set Programming [7] is a logic-based language that has been successfully applied to model combinatorial domains. When the information is uncertain, we can adopt the Credal Semantics, that gives a meaning to Answer Set Programs extended with probabilistic facts [2]. These programs are called Probabilistic Answer Set Programs (PASP).

More than 30 years ago, Halpern [8] introduced the so-called "Type 1 statments", also known as "probabilistic conditionals" or "statistical statements", that allow expressing statistical information about a domain of interest. An example of such a statement is "X% of elements of a domain have the property Y". Recently, the authors of [9] introduced the possibility to express Type 1 statements with Probabilistic Answer Set Programming, that are converted into a disjunctive rule and a constraint with aggregates, and provided a framework called PASTA.

Inference in PASP has been proved hard [6,10,11]. For example, the inference task (i.e., the computation of the probability of a query) for propositional programs lies in the PP NP complexity class for programs allowing disjunctive rules only, where PP represents the class of the decision problems that can be solved in polynomial time with a probabilistic Turing machine [12]. If we add stratified negation the complexity jumps to the PP Σ p 2 class of the polynomial hierarchy [13]. Also in practice, inference in such programs is very expensive [9,14].

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 efficiently 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.

Background

Answer Set Programming

Answer Set Programming [7] (ASP) is one of the possible logic-based languages suitable to model combinatorial domains. An answer set program is composed by a set of disjunctive rules of the form ℎ 0 ; . . . ; ℎ 𝑚 : − 𝑏 0 , . . . , 𝑏 𝑛 where ℎ 0 ; . . . ; ℎ 𝑚 is a disjunction of atoms called head and 𝑏 0 , . . . , 𝑏 𝑛 is a conjunction of literals called body. We use 𝑛𝑜𝑡 to denote negation. Head and body may be empty: if the heady is empty (but the body is not), the rule is called constraint; conversely, if the head has only one atom and the body is empty, it is called fact. An example of disjunctive rule is 𝑎; 𝑏 : − 𝑐, where 𝑎; 𝑏 is the head and 𝑐 is the body. Another construct often adopted in answer set programs are aggregates [15]. An aggregate has the form 𝑡 0 𝜓 0 #𝑓 {𝑒 0 ; . . . ; 𝑒 𝑛 }𝜓 1 𝑡 1 , where the 𝑒 𝑖 s are aggregate terms of the form 𝑡 0 , . . . , 𝑡 𝑘 : 𝜙 where each 𝑡 0 is a term and 𝜙 is a conjunction of literals, 𝑓 is an aggregation function such as 𝑐𝑜𝑢𝑛𝑡 or 𝑠𝑢𝑚, 𝜓 0 and 𝜓 1 are arithmetic comparison operators, and 𝑡 0 and 𝑡 1 are constants. An example of aggregate is #𝑐𝑜𝑢𝑛𝑡{𝑋 : 𝑎(𝑋)} > 3.

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. It has two answer sets: {𝑎, 𝑞𝑎, 𝑏, 𝑛𝑞𝑏} and {𝑎, 𝑞𝑎, 𝑏, 𝑞𝑏}.

Probabilistic Answer Set Programming

To describe uncertain scenarios with Answer Set Programming, several semantics have been proposed, such as LPMLN [17], P-log [18], and the credal semantics [11]. Here we focus on the credal semantics, which extends an answer set program with probabilistic facts [2] of the form Π :: 𝑎.

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 [5]

𝑃 (𝑤) = ∏︁ 𝑎 𝑖 ∈𝑤 𝑃 (𝑎 𝑖 ) • ∏︁ 𝑎 𝑖 ̸ ∈𝑤 1 − 𝑃 (𝑎 𝑖 )

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. q:-qa. q:-qb.

It has 2 2 = 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 [8], also known as probabilistic conditionals, allow representing statistical information about a domain, such as "X% of domain elements have the property Y". The authors of [9,19] introduced the possibility of encoding such statements within a PASP with the syntax:

(𝐶 | 𝐴)[Π 𝑙 , Π 𝑢 ]

where 𝐶 and 𝐴 are (conjunction of) atoms and Π 𝑙 , Π 𝑢 ∈ [0, 1], Π 𝑙 ≤ Π 𝑢 . We call 𝐶 consequent and 𝐴 antecedent. The meaning is "the fraction of 𝐴s that have the property 𝐶 is between Π 𝑙 and Π 𝑢 ". To perform inference, a statement is converted into a disjunctive rule with the structure 𝐶; 𝑛𝑜𝑡_𝐶 : − 𝐴, describing that the property 𝐶 may or may not hold for each element 𝐴, and a constraint with counting aggregates imposing the specified probability bound, i.e., imposing

Π 𝑙 ≤ #𝑐𝑜𝑢𝑛𝑡{X : 𝐴(X), 𝐶(X)} #𝑐𝑜𝑢𝑛𝑡{X : 𝐴(X)} ≤ Π 𝑢 .

Let us clarify it by discussing the following example from [9].

Example 3 (from [9]). The following program has 3 probabilistic facts and one statistical statement.

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: 0.4::bird(1). 0.4::bird(2). 0.4::bird(3). fly(X) ; not_fly(X) :-bird(X). b1 :-bird(1). b1 :-bird(2). b1 :-bird(3). :-b1, not fb1 . b2 :-bird(1), bird(2). b2 :-bird(1), bird(3). b2 :-bird(2), bird(3). :-b2, not fb2 . b3 :-bird (1), bird (2), bird (3). :-b3, not fb2. fb1 :-fly(1). fb1 :-fly(2). fb1 :-fly(3). fb2 :-fly(1), fly(2). fb2 :-fly(1), fly(3). fb2 :-fly(2), fly(3).

In the remaining part of the paper we refer to "PASTA programs" by programs comprising a set of probabilistic facts as well as a set of disjunctive rules and constraints with counting aggregates.

Computational Complexity

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 PP NP -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 [10].

The Complexity of PASTA Inference

We obtain the following complexity results, which underline the simplicity of inference for PASTA programs. As in [10], we focus here on the complexity of cautious reasoning, i.e., given a set of ground literals 𝑄 (query), a set of ground atoms 𝐸 (evidence), and a real number 𝛾, deciding whether P(𝑄 | 𝐸) ≥ 𝛾. As also noted in [10], the computation of the upper probability reduces to the computation of the lower probability on the complement set of 𝑄. To lighten the notation, we simply refer to the cautious reasoning task as inference task.

Theorem 1 (Complexity). Inference in PASTA programs under credal semantics is PP NP -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 0.5::t(𝑥).

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 𝑦 ∈ 𝑌 :

t(y) ; f(y).

For every DNF term 𝑐, every positive variable 𝑣 𝑖 in 𝑐 and every negative occurrence ¬𝑣 𝑗 add:

pos(𝑐, 𝑣 𝑖 ). neg(𝑐, 𝑣 𝑗 ).

We have satisfiability if and only if at least one DNF term is satisfied:

:-#count {C : sat(C)}=T, #count {1: sat}=S, T<S.

:-#count {C : nsat(C)}=T, #count {1: nsat}=S, S*|𝜙| >T.

For the satisfied DNF terms 𝑐 we add the following constraint:

:-#count {V : t(V), pos(𝑐,V); V : not t(V), neg(𝑐,V)}=T, #count {1 : sat(𝑐)}=S, T<3S.

For the unsatisfied DNF terms 𝑐 we do the following :-#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 PP NP 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 0.5::t(𝑥).

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 2 3 cases): 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.

:-#count { C: t(V1), t(

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 known relationship [10, Eqs (4)] P(𝐴 | 𝐵) = 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(𝐴 | 𝐵).

Related Work

Different 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 [6,10,11]. The inference task goes up several levels of the polynomial hierarchy depending on the allowed syntactic constructs such as disjunctive rules, negation (either stratified or non-stratified), and aggregates. However, this seems the price to pay to use a rich and expressive language. Statistical statements are also discussed in [27], where the author provides a semantics based on the cross entropy minimization. The approach considered in PASTA is different, since it does not focus on a single model but it considers multiple models and lower and upper probability bounds.

Conclusion

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 PP NP -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.