[Back]

M. Alviano, W. Faber, S. Woltran:
"Complexity of Super-Coherence Problems in ASP";
Talk: Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP) 2010, Lexington, Kentucky, USA; 07-06-2011 - 07-10-2011.

Adapting techniques from database theory in order to optimize Answer
Set Programming (ASP) systems, and in particular the grounding components of ASP systems, is an important topic in ASP. In recent years, theMagic Set method has received some interest in this setting, and a variant of it, called DMS, has been proposed for ASP. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all ASP programs. In recent
work, a large fragment of ASP programs, referred to as super-coherent programs, has been identified, for which DMS is correct. An open question remained: How complex is it to determine whether a given program is super-coherent? This question turned out to be quite difficult to answer precisely. In this paper, we formally prove that deciding whether a propositional program is super-coherent is P
3 - complete in the disjunctive case, while it is P 2 -complete for normal programs. The hardness proofs are the difficult part in this endeavor:We proceed by characterizing the reductions by the models and reduct models which the ASP programs should have, and then provide instantiations that meet the given specifications.