systems are continuously enhanced to support novel optimization strategies, enabling them to be effective over increasingly larger application domains.

Frequently, optimization techniques are inspired by methods that had been proposed in other fields, for example database theory, satisfiability solving, or constraint satisfaction. Among techniques adapted to ASP from database theory, Magic Sets [@ullm-89; @banc-etal-86; @beer-rama-91] have recently achieved a lot of attention. Following some earlier work [@grec-2003; @cumb-etal-2004-iclp], an adapted method called *DMS* has been proposed for [$\rm ASP$]{} in [@alvi-etal-2012-aij]. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all [$\rm ASP$]{} programs. In recent work [@alvi-fabe-2011-aicom; @alvi-fabe-2010-aspocp], a large fragment of ASP programs, referred to as *super-coherent programs* ([$\rm ASP^{\rm sc}$]{}), has been identified, for which DMS can be proved to be correct. Formally, a program is super-coherent, if it is coherent (i.e. possesses at least one answer set), no matter which input (given as a set of facts) is added to the program.

Since the property of being super-coherent is a semantic one, a natural question arises: How difficult is it to decide whether a given program belongs to [$\rm ASP^{\rm sc}$]{}? It turns out that the precise 