complexity is rather difficult to establish. Some bounds have been given in [@alvi-fabe-2011-aicom], in particular showing decidability, but especially hardness results seemed quite hard to obtain. In particular, the following question remained unanswered: Is it possible to implement an efficient algorithm for testing super-coherence of a program, to decide for example whether DMS has to be applied or not? In this paper we provide a negative answer to this question, proving that deciding whether a propositional program is super-coherent is complete for the third level of the polynomial hierarchy in the general case, and for the second level for normal programs. As the complexity of query answering is located on lower levels of the polynomial hierarchy, our results show that implementing a sound and complete super-coherence check in a query optimization setting does not provide an approach for improving such systems.

While our main motivation for studying [$\rm ASP^{\rm sc}$]{} stemmed from the applicability of DMS, this class actually has many more important motivations. Indeed, it can be viewed as the class of *non-constraining programs*: Adding extensional information to these programs will always result in answer sets. One important implication of this property is for modular evaluation. For instance, when 