  In this paper, we focus on the problem of existence and computing of small
and large stable models. We show that for every fixed integer k, there is a
linear-time algorithm to decide the problem LSM (large stable models problem):
does a logic program P have a stable model of size at least |P|-k. In contrast,
we show that the problem SSM (small stable models problem) to decide whether a
logic program P has a stable model of size at most k is much harder. We present
two algorithms for this problem but their running time is given by polynomials
of order depending on k. We show that the problem SSM is fixed-parameter
intractable by demonstrating that it is W[2]-hard. This result implies that it
is unlikely, an algorithm exists to compute stable models of size at most k
that would run in time O(n^c), where c is a constant independent of k. We also
provide an upper bound on the fixed-parameter complexity of the problem SSM by
showing that it belongs to the class W[3].
