Backdoors to tractable answer set programming

Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many AI problems such as reasoning in a nonmonotonic setting can be directly f...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2015-03, Vol.220, p.64-103
Main Authors: Fichte, Johannes Klaus, Szeider, Stefan
Format: Article
Language:English
Subjects:
Answer set programming
Artificial intelligence
Backdoors
Complexity theory
Computational complexity
Constrictions
Expert systems
Hierarchies
Kernelization
Logic programming
Parameterized complexity
Polynomials
Programming
Reasoning
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many AI problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable. In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent “clever reasoning shortcuts” through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming.
ISSN:0004-3702
1872-7921
DOI:10.1016/j.artint.2014.12.001