to our theory.

Finally, we need to express that Joe doesn't lose money by selling his items.

This is done by the aggregate sumh{b1 = w1, . . . , bn = wn,¬s1 = −c1, . . . ,¬sm = −cm**}i ≥** 0, (20)
where each wiis the amount of money (possibly negative) obtained by accepting bid i, and each ciis the money requested by the junkyard to remove item i. Note that (20) is neither monotone nor antimonotone.

We define a *solution* to Joe's problem as a set of accepted bids such that
(a) the bids involve selling disjoint sets of items, and
(b) the sum of the money earned from the bids is greater than the money spent giving away the remaining items.

Proposition 14. X **7→ {**i : bi ∈ X} *is a 1–1 correspondence between the stable models of the theory consisting of formulas (17)–(20) and a solution to Joe's* problem.

## 3.5 Computational Complexity

Since theories with aggregates generalize disjunctive programs, the problem of the existence of a stable model of a theory with aggregates clearly is Σ
P 2
-hard.11 We need to check in which class of the computational hierarchy this problem belongs.

Even if propositional formulas corresponding to aggregates can be exponentially larger than the original aggregate, it turns out that (by treating aggregates as primitive constructs) the computation is not harder than for propositional theories.

Proposition 15. If, for every aggregate, computing op(W) ≺ N *requires polynomial time then the existence of a stable model of a theory with aggregates is a* Σ
P 2
-complete problem.

For a nondisjunctive program with nested expressions the existence of a stable model is NP-complete. If we allow nonnested aggregates in the body, for instance by allowing rules A1 **∧ · · · ∧** An → a
(A1, . . . , An are aggregates and a is an atom or ⊥) then the complexity increases to Σ
P
2
. This follows from Lemma 1, since, in (5), each formula liis the propositional