Complexity of Answer Set Checking and Bounded Predicate Arities for Non-ground Answer Set Programming.
Thomas Eiter, Wolfgang Faber, Michael Fink, Gerald Pfeifer, Stefan Woltran · 2003
We present new complexity results on answer set checking for nonground programs under a variety of syntactic restrictions. For several of these problems, the kind of representation of the answer set to be checked is important. In particular, we consider set-based and bitmap-based representations, which are popular in implementations of Answer Set Programming systems. Furthermore, we present new complexity results for various reasoning tasks under the assumption that predicate arities are bounded by some constant. These results imply that in such a setting -- which appears to be a reasonable assumption in practice -- more efficient implementations than those currently available may be feasible. 1