problem for the case of disjunctive logic programs and non-disjunctive (normal) logic programs. We first have a look at a similar problem, which turns out to be rather trivial to decide.

The problem of deciding whether, for a given disjunctive program $P$, there is a set $F$ of facts such that ${{\mathit AS}}(P\cup F)\neq\emptyset$ is ${\ensuremath{\mathrm{NP}}}$-complete; ${\ensuremath{\mathrm{NP}}}$-hardness holds already for normal programs.

We start by observing that there is $F$ such that ${{\mathit AS}}(P\cup F)\neq\emptyset$ if and only if $P$ has at least one model. Indeed, if $M$ is a model of $P$, then $P\cup M$ has $M$ as its answer set. On the other hand, if $P$ has no model, then no addition of facts $F$ will yield an answer set for $P\cup F$. It is well known that deciding whether a program has at least one (classical) model is ${\ensuremath{\mathrm{NP}}}$-complete for both disjunctive and normal programs.

In contrast, the complexity for deciding super-coherence is surprisingly high, which we shall show next. To start, we give a straight-forward observation.

\[prop:restrict\] A program $P$ is super-coherent if and only if for each set $F\subseteq {{\mathit At}}(P)$, ${{\mathit AS}}(P\cup F)\neq\emptyset$.

The only-if direction is by definition. For the if-direction, let $F$ 