English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Answer Set Programming (ASP) is a paradigm for modeling and solving problemsfor knowledge representation and reasoning. There are plenty of resultsdedicated to studying the hardness of (fragments of) ASP. So far, these studiesresulted in characterizations in terms of computational complexity as well asin fine-grained insights presented in form of dichotomy-style results, lowerbounds when translating to other formalisms like propositional satisfiability(SAT), and even detailed parameterized complexity landscapes. A genericparameter in parameterized complexity originating from graph theory is theso-called treewidth, which in a sense captures structural density of a program.Recently, there was an increase in the number of treewidth-based solversrelated to SAT. While there are translations from (normal) ASP to SAT, noreduction that preserves treewidth or at least keeps track of the treewidthincrease is known. In this paper we propose a novel reduction from normal ASPto SAT that is aware of the treewidth, and guarantees that a slight increase oftreewidth is indeed sufficient. Further, we show a new result establishingthat, when considering treewidth, already the fragment of normal ASP isslightly harder than SAT (under reasonable assumptions in computationalcomplexity). This also confirms that our reduction probably cannot besignificantly improved and that the slight increase of treewidth isunavoidable. Finally, we present an empirical study of our novel reduction fromnormal ASP to SAT, where we compare treewidth upper bounds that are obtainedvia known decomposition heuristics. Overall, our reduction works better withthese heuristics than existing translations.

Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?