  We study the following problem: given a class of logic programs C, determine
the maximum number of stable models of a program from C. We establish the
maximum for the class of all logic programs with at most n clauses, and for the
class of all logic programs of size at most n. We also characterize the
programs for which the maxima are attained. We obtain similar results for the
class of all disjunctive logic programs with at most n clauses, each of length
at most m, and for the class of all disjunctive logic programs of size at most
n. Our results on logic programs have direct implication for the design of
algorithms to compute stable models. Several such algorithms, similar in spirit
to the Davis-Putnam procedure, are described in the paper. Our results imply
that there is an algorithm that finds all stable models of a program with n
clauses after considering the search space of size O(3^{n/3}) in the worst
case. Our results also provide some insights into the question of
representability of families of sets as families of stable models of logic
programs.
