Computer Science – Computational Complexity
Scientific paper
2011-04-14
Computer Science
Computational Complexity
Scientific paper
We present a unifying approach to the efficient evaluation of propositional answer-set programs. Our approach is based on backdoors which are small sets of atoms that represent "clever reasoning shortcuts" through the search space. The concept of backdoors is widely used in the areas of propositional satisfiability and constraint satisfaction. We show how this concept can be adapted to the nonmonotonic setting and how it allows to augment various known tractable subproblems, such as the evaluation of Horn and acyclic programs. In order to use backdoors we need to find them first. We utilize recent advances in fixed-parameter algorithmics to detect small backdoors. This implies fixed-parameter tractability of the evaluation of propositional answer-set programs, parameterized by the size of backdoors. Hence backdoor size provides a structural parameter similar to the treewidth parameter previously considered. We show that backdoor size and treewidth are incomparable, hence there are instances that are hard for one and easy for the other parameter. We complement our theoretical results with first empirical results.
Fichte Johannes Klaus
Szeider Stefan
No associations
LandOfFree
Backdoors to Tractable Answer-Set Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Backdoors to Tractable Answer-Set Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Backdoors to Tractable Answer-Set Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-166878