[Back]

M. Hecher:
"Treewidth-aware Reductions of Normal {ASP} to {SAT} - Is Normal {ASP} Harder than {SAT} after All?";
Talk: KR 2020 - 17th International Conference on Principles of Knowledge Representation and Reasoning, Rhodos, Griechenland; 2020-09-12 - 2020-09-18; in: "Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, {KR} 2020, Rhodes, Greece, September 12-18, 2020", (2020), 485 - 495.

Answer Set Programming (ASP) is a paradigm and problem modeling/solving toolkit for KR that is often invoked. There are plenty of results dedicated to studying the hardness of (fragments of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A quite generic and prominent parameter in parameterized complexity originating from graph

theory is the so-called treewidth, which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there exist several translations from (normal) ASP to SAT, yet there is no reduction preserving treewidth or at least

being aware of the treewidth increase. This paper deals with a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Then, we also present a new result establishing that when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable.

Computational aspects of knowledge representation-General Logic programming, answer set programming, constraint logic programming-General Nonmonotonic logics, default logics, conditional logics-General

http://dx.doi.org/10.24963/kr.2020/49

Project Head Stefan Woltran:
HYPAR

Project Head Stefan Woltran:
START