
| monotone/antimonotone   | generic     | anti-chain      |     |
|-------------------------|-------------|-----------------|-----|
| aggregates              | aggregates  | property        |     |
| weight constraints      | NP-complete | NP-complete     | NO  |
| PDB-aggregates          | NP-complete | Σ 2 P -complete | YES |
| FLP-aggregates          | NP-complete | Σ 2 P -complete | YES |
| our aggregates          | NP-complete | Σ 2 P -complete | NO  |

Figure 4: Properties of definitions of programs with aggregates, in the case in which the head of each rule is an atom. We limit the syntax of our aggregates to the syntax allowed by the other formalisms. The complexity is relative to the problem of the existence of a stable model. The anti-chain property holds when no stable model can be a subset of another one.

representation of sumh{li = 1**}i ≥** 1; similarly, each aj → aiis the propositional representation of sumh{aj = −1, ai = 1**}i ≥** 0.

However, if we allow monotone and antimonotone aggregates only - even nested - in the antecedent, we are in class NP. Proposition 16. Consider theories with aggregates consisting of formulas of the form F → a, where a is an atom or ⊥, and F contains monotone and antimonotone aggregates only, no equivalences and no implications other than negations. If, for every aggregate, computing op(W) ≺ N requires polynomial time then the problem of the existence of a stable model of theories of this kind is an NP-complete problem.

Similar results have been independently proven in [Calimeri *et al.*, 2005] for FLP-aggregates.

## 3.6 Other Formalisms

Figure 4 already shows that there are several differences between the various definitions of an aggregate. We analyze that more in details in the rest of this section.

## 3.6.1 Programs With Weight Constraints

Weight constraints are aggregates defined in [Niemel¨a and Simons, 2000] and implemented in answer set solver SMODELS. We simplify the syntax of weight constraints and of programs with weight constraints for clarity, without reducing its semantical expressivity.