[Back]


Talks and Poster Presentations (without Proceedings-Entry):

M. Hecher:
"Treewidth-Aware Reductions of normal ASP to SAT - Is normal ASP harder than SAT after all?";
Talk: 4th Workshop on Trends and Applications of Answer Set Programming (TAASP 2020), Klagenfurt; 2020-11-23 - 2020-11-24.



English abstract:
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.


Related Projects:
Project Head Stefan Woltran:
HYPAR

Project Head Stefan Woltran:
START


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