be any set of facts. $F$ can be partitioned into $F' = F \cap {{\mathit At}}(P)$ and $F'' = F \setminus F'$. By assumption, $P$ is super-coherent and thus $P \cup F'$ is coherent. Let $M$ be an answer set of $P \cup F'$. We shall show that $M \cup F''$ is an answer set of $P \cup F = P \cup F' \cup F''$. This is in fact a consequence of the splitting set theorem [@lifs-turn-94], as the atoms in $F''$ are only defined by facts not occurring in $P \cup F'$.

Our main results are stated below. The proofs are contained in the subsequent sections.

\[thm:disj\] The problem of deciding super-coherence for disjunctive programs is ${\ensuremath{{\Pi}_{3}^{P}}}$-complete.

\[thm:norm\] The problem of deciding super-coherence for normal programs is ${\ensuremath{{\Pi}_{2}^{P}}}$-complete.

Proof of Theorem \[thm:disj\] {#sec:proofdisj}
-----------------------------

Membership follows by the following straight-forward nondeterministic algorithm for the complementary problem, i.e. given a program $P$, does there exist a set $F$ of facts such that ${{\mathit AS}}(P\cup F)=\emptyset$: we guess a set $F\subseteq {{\mathit At}}(P)$ and check ${{\mathit AS}}(P\cup F)=\emptyset$ via an oracle-call. Restricting the guess to ${{\mathit At}}(P)$ can be done by Proposition \[prop:restrict\]. Checking ${{\mathit AS}}(P\cup F)=\emptyset$ is known to be 