  We present trichotomy results characterizing the complexity of reasoning with
disjunctive logic programs. To this end, we introduce a certain definition
schema for classes of programs based on a set of allowed arities of rules. We
show that each such class of programs has a finite representation, and for each
of the classes definable in the schema we characterize the complexity of the
existence of an answer set problem. Next, we derive similar characterizations
of the complexity of skeptical and credulous reasoning with disjunctive logic
programs. Such results are of potential interest. On the one hand, they reveal
some reasons responsible for the hardness of computing answer sets. On the
other hand, they identify classes of problem instances, for which the problem
is "easy" (in P) or "easier than in general" (in NP). We obtain similar results
for the complexity of reasoning with disjunctive programs under the
supported-model semantics. To appear in Theory and Practice of Logic
Programming (TPLP)
