J. Fichte, S. Szeider:

"Backdoor Trees for Answer Set Programming";

Report No. DBAI-TR-2016-98, 2016; 24 pages.

Answer set programming (ASP) is a popular framework for declarative modelling and problem solving. It has successfully been used to solve a wide variety of problems in artificial intelligence and reasoning. Many problems in propositional disjunctive ASP are of high computational complexity, such as reasoning, counting, and enumeration; in particular, the reasoning problems are complete for the second level of the Polynomial Hierarchy and thus even harder than NP. In this paper, we introduce backdoor trees for ASP and present a parameterized complexity analysis that takes the input size of an instance along with a composed parameter, which is based on backdoor trees, into account. When using backdoors for a parameterized complexity analysis one only considers the size k of a backdoor as a parameter. Evaluating a given backdoor results in 2^k assignments and thus 2^k programs the assignments. However, an assignment to fewer than k atoms can already yield a program under assignment that belongs to the fixed target class. Therefore, we consider binary decision trees, which make gradually assigning truth values to backdoor atoms in a program precise and lead us to the notion of backdoor trees, originally defined for propositional satisfiability. In this way, backdoor trees provide a more precise approach to the evaluation of backdoors, where we take the interaction of the assignments in the evaluation into account.

Project Head Stefan Woltran:

START

Created from the Publication Database of the Vienna University of Technology.