KR Conference 2012 Conference Paper
- Wolfgang Dvorak
- Matti Järvisalo
- Johannes Peter Wallner
- Stefan Woltran
of this paper is both on the identification of such lowercomplexity fragments of second-level reasoning problems arising from abstract argumentation, and on exploiting this knowledge in developing efficient complexity-sensitive decision procedures for the generic second-level problems. Tractable (i. e., polynomial-time decidable) fragments have been quite thoroughly studied in the literature (see, e. g., (Coste-Marquis, Devred, and Marquis 2005; Dunne 2007; Dvořák, Szeider, and Woltran 2010; Dvořák, Pichler, and Woltran 2011; Ordyniak and Szeider 2011)). However, there is only little work on the identification of fragments which are located on the first level (NP-coNP layer), that is, inbetween tractability and full second-level complexity. Identification of first-level fragments of second-level reasoning tasks is important due to several reasons. First, from a theoretical point of view, such fragments show particular (but not all) sources of complexity of the considered problems and pave the way towards “trichotomy”-like results (e. g. (Truszczynski 2011) in the context of answer-set programming). Second, NP fragments can be efficiently reduced to the problem of satisfiability in classical propositional logic (SAT). This allows for realizations of argumentation procedures by employing highly sophisticated SAT solver technology in reasoning on argumentation problems. Going even further, we aim at designing decision procedures for larger fragments based on decision procedures developed for an NP-fragment, using the NP decision procedures as an NP oracle in an iterative fashion. Such procedures fall under the general counter-example guided abstraction refinement (CEGAR) approach originating from the field of model checking (Clarke et al. 2003; Clarke, Gupta, and Strichman 2004). For problems complete for the second level of the polynomial hierarchy, this leads to a general procedure which, in the worst case, requires an exponential number of calls to the NP oracle, which is indeed unavoidable under the assumption that the polynomial hierarchy does not collapse. Nevertheless, such procedures can be designed to behave adequately on input instances that fall into the considered NP fragment and on instances for which a relatively low number of oracle calls is sufficient. As a generic notion, we say that such a procedure is complexity-sensitive w. r. t. the NP fragment at hand. For instance, for the second level problem of answer-set existence for disjunctive logic programs, the successful loop-formula Abstract argumentation frameworks (AFs) provide the basis for various reasoning problems in the areas of Knowledge Representation and Artificial Intelligence. Efficient evaluation of AFs has thus been identified as an important research challenge. So far, implemented systems for evaluating AFs have either followed a straight-forward reduction-based approach or been limited to certain tractable classes of AFs. In this work, we present a generic approach for reasoning over AFs, based on the novel concept of complexity-sensitivity. Establishing the theoretical foundations of this approach, we derive several new complexity results for preferred, semistable and stage semantics which complement the current complexity landscape for abstract argumentation, providing further understanding on the sources of intractability of AF reasoning problems. The introduced generic framework exploits decision procedures for problems of lower complexity whenever possible. This allows, in particular, instantiations of the generic framework via harnessing in an iterative way current sophisticated Boolean satisfiability (SAT) solver technology for solving the considered AF reasoning problems. First experimental results show that the SAT-based instantiation of our novel approach outperforms existing systems.