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


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



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


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.




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.



AAAI Technical Track on Knowledge Representation and Reasoning