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. Concerning the second question, we show that all relevant ASP reasoning tasks can be transformed into tasks over super-coherent programs, even though this transformation is more of theoretical than practical interest.'
author:
- |
    MARIO ALVIANO and WOLFGANG FABER\
    University of Calabria, 87036 Rende (CS), Italy\
- |
    STEFAN WOLTRAN\
    Vienna University of Technology, 1040 Vienna, Austria\
bibliography:
- 'supercoherent.bib'
title: 'Complexity of Super-Coherence Problems in ASP [^1] '
---

\[firstpage\]

Answer-Set Programming, Complexity Analysis

Introduction {#sec:introduction}
============

Answer Set Programming ([$\rm ASP$]{}) is a powerful formalism for knowledge representation and common sense reasoning [@bara-2002]. Allowing disjunction in rule heads and nonmonotonic negation in bodies, [$\rm ASP$]{} can express every query belonging to the complexity class $\rm{\ensuremath{\Sigma_{2}^P}}$ (${\ensuremath{\mathrm{NP}}}^{\ensuremath{\mathrm{NP}}}$). Encouraged by the availability of efficient inference engines, such as DLV [@leon-etal-2002-dlv], GnT [@janh-etal-2005-tocl], Cmodels [@lier-2005-lpnmr], or ClaspD [@dres-etal-2008-KR], [$\rm ASP$]{} has found several practical applications in various domains, including data integration [@leon-etal-2005], semantic-based information extraction [@manna-etal-2011-tldks; @manna-etal-2011-jcss], e-tourism [@ricca-etal-2010-IDUM], workforce management [@ricca-etal-2012-tplp], and many more. As a matter of fact, these [$\rm ASP$]{} 