caa a22 4500 463186966 CHVBK 20180406164856.0 cr unu---uuuuu 170326e20071201xx s 000 0 eng 10.1007/s10472-008-9086-5 doi (NATIONALLICENCE)springer-10.1007/s10472-008-9086-5 Complexity results for answer set programming with bounded predicate arities and implications [Elektronische Daten] [Thomas Eiter, Wolfgang Faber, Michael Fink, Stefan Woltran] Answer set programming is a declarative programming paradigm rooted in logic programming and non-monotonic reasoning. This formalism has become a host for expressing knowledge representation problems, which reinforces the interest in efficient methods for computing answer sets of a logic program. The complexity of various reasoning tasks for general answer set programming has been amply studied and is understood quite well. In this paper, we present a language fragment in which the arities of predicates are bounded by a constant. Subsequently, we analyze the complexity of various reasoning tasks and computational problems for this fragment, comprising answer set existence, brave and cautious reasoning, and strong equivalence. Generally speaking, it turns out that the complexity drops significantly with respect to the full non-ground language, but is still harder than for the respective ground or propositional languages. These results have several implications, most importantly for solver implementations: Virtually all currently available solvers have exponential (in the size of the input) space requirements even for programs with bounded predicate arities, while our results indicate that for those programs polynomial space should be sufficient. This can be seen as a manifestation of the "grounding bottleneck” (meaning that programs are first instantiated and then solved) from which answer set programming solvers currently suffer. As a final contribution, we provide a sketch of a method that can avoid the exponential space requirement for programs with bounded predicate arities. Springer Science+Business Media B.V., 2008 Answer set programming nationallicence Computational complexity nationallicence Eiter Thomas Institute of Information Systems, Vienna University of Technology, Vienna, Austria aut Faber Wolfgang Department of Mathematics, University of Calabria, Rende, Italy aut Fink Michael Institute of Information Systems, Vienna University of Technology, Vienna, Austria aut Woltran Stefan Institute of Information Systems, Vienna University of Technology, Vienna, Austria aut Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/2-4(2007-12-01), 123-165 1012-2443 51:2-4<123 2007 51 10472 https://doi.org/10.1007/s10472-008-9086-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10472-008-9086-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Eiter Thomas Institute of Information Systems, Vienna University of Technology, Vienna, Austria aut NATIONALLICENCE 700 1- Faber Wolfgang Department of Mathematics, University of Calabria, Rende, Italy aut NATIONALLICENCE 700 1- Fink Michael Institute of Information Systems, Vienna University of Technology, Vienna, Austria aut NATIONALLICENCE 700 1- Woltran Stefan Institute of Information Systems, Vienna University of Technology, Vienna, Austria aut NATIONALLICENCE 773 0- Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/2-4(2007-12-01), 123-165 1012-2443 51:2-4<123 2007 51 10472 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer