rules to the associated program. A query ${\ensuremath{\mathit{q}}}$ is *bravely* true for a program $P$ if and only if $q\in A$ for some $A \in {{\mathit AS}}(P)$. A query ${\ensuremath{\mathit{q}}}$ is *cautiously* true for a program $P$ if and only if $q\in A$ for all $A \in {{\mathit AS}}(P)$.

We now introduce super-coherent ASP programs ([$\rm ASP^{\rm sc}$]{} programs), the main class of programs studied in this paper.

A program ${P}$ is *super-coherent* if, for every set of facts $F$, ${{\mathit AS}}({P}\cup F) \neq \emptyset$. Let [$\rm ASP^{\rm sc}$]{} denote the set of all super-coherent programs.

Note that [$\rm ASP^{\rm sc}$]{} programs include all odd-cycle-free programs (and therefore also all stratified programs). Indeed, every odd-cycle-free program admits at least one answer set and remains odd-cycle-free even if an arbitrary set of facts is added to its rules. On the other hand, there are programs having odd-cycles that are in [$\rm ASP^{\rm sc}$]{}, cf. [ ]{}.

Complexity of Checking Super-Coherence {#sec:statement}
======================================

In this section, we study the complexity of the following natural problem:

-   Given a program $P$, is $P$ super-coherent, i.e.  does ${{\mathit AS}}(P\cup F)\neq\emptyset$ hold for any set $F$ of facts.

We will study the complexity for this 