J. Fandinno,M. Hecher:

"Treewidth-Aware Complexity in {ASP:} Not all Positive Cycles are Equally Hard";

Talk: 35th AAAI 2021, virtual event; 2021-02-02 - 2021-02-09; in: "Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021", (2021), 6312 - 6320.

It is well-known that deciding consistency for normal answer set programs (ASP) is NP-complete, thus, as hard as the satisfaction problem for propositional logic (SAT). The exponential time hypothesis (ETH) implies that the best algorithms to solve these problems take exponential time in the worst case. However, accounting for the treewidth, the consistency problem for ASP is slightly harder than SAT: while SAT can be solved by an algorithm that runs in exponential time in the treewidth k, ASP requires exponential time in k · log(k). This extra cost is due to checking that there are no self-supported true atoms due to positive cycles in the program. In this paper, we refine this recent result and show that consistency for ASP can be decided in exponential time in k · log(ι) where ι is a novel measure, bounded by both treewidth k and the size of the largest strongly-connected component of the positive dependency graph of the program. We provide a treewidth-aware reduction from ASP to SAT that adheres to the above limit.

Computational Complexity of Reasoning, Logic Programming, Nonmonotonic Reasoning, Other Foundations of Knowledge Representation

Project Head Stefan Woltran:

START

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