Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard

Authors

  • Jorge Fandinno University of Nebraska Omaha University of Potsdam
  • Markus Hecher University of Potsdam TU Wien

Keywords:

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

Abstract

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.

Downloads

Published

2021-05-18

How to Cite

Fandinno, J., & Hecher, M. (2021). Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6312-6320. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16784

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning