  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, located at 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 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.
