challenging topic for future research.

To summarize, the main contributions of the paper are as follows:

-   We show that recognizing super-coherence for disjunctive and normal programs is complete for classes ${\ensuremath{{\Pi}_{3}^{P}}}$ and ${\ensuremath{{\Pi}_{2}^{P}}}$, respectively, thus more complex than the common ASP reasoning tasks.

-   We provide a transformation of reasoning tasks over general programs into tasks over super-coherent programs, showing that the restriction to super-coherent programs does not curtail expressive power.

-   We also briefly discuss the relation between checking for super-coherence and testing equivalence between programs where we make use of our results to sharpen complexity results due to [ ]{}.

In order to focus on the essentials of these problems, in this paper we deal with propositional programs, but we conjecture that the results can be extended to the non-propositional case by using complexity upgrading techniques as presented in [@eite-etal-97-tods; @gott-etal-99apal], arriving at completeness for classes [$\mbox{\rm co-}{\ensuremath{\mathrm{NEXP}}}^{{\ensuremath{\mathrm{NP}}}}$]{} and [$\mbox{\rm co-}{\ensuremath{\mathrm{NEXP}}}^{{\ensuremath{\Sigma_{2}^P}}}$]{}, respectively.

The remainder of this article is organized as follows. In Section \[sec:preliminaries\] we first define some terminology needed later on. In Section \[sec:statement\] we formulate the complexity problems that we analyze, and state our main results. The proofs for these problems are presented in Section 