[Back]

J. Fandinno, M. Hecher:
"Treewidth-Aware Complexity in ASP:Not all Positive Cycles are Equally Hard";
Talk: NMR 2020 - 18th INTERNATIONAL WORKSHOP ON NON-MONOTONIC REASONING, Rhodos, Griechenland; 2020-09-12 - 2020-09-18; in: "18th INTERNATIONAL WORKSHOP ONNON-MONOTONIC REASONING", (2020), 48 - 57.

It is well-know that deciding consistency for normal answer setprograms (ASP) is NP-complete, thus, as hard as the satisfac-tion problem for classical propositional logic (SAT). The bestalgorithms to solve these problems take exponential time inthe worst case. Theexponential time hypothesis(ETH) impliesthat this result is tight for SAT, that is, SAT cannot be solved insubexponential time. This immediately establishes that the re-sult is also tight for the consistency problem for ASP. However,accounting for the treewidth of the problem, the consistencyproblem for ASP is slightly harder than SAT: while SAT canbe solved by an algorithm that runs in exponential time in thetreewidthk, it was recently shown that ASP requires exponen-tial time ink·log(k). This extra cost is due checking thatthere are no self-supported true atoms due to positive cycles inthe program. In this paper, we refine the above result and showthat the consistency problem for ASP can be solved in expo-nential time ink·log(λ)whereλis the minimum betweenthe treewidth and the size of the largest strongly-connectedcomponent in the positive dependency graph of the program.We provide a dynamic programming algorithm that solves theproblem and a treewidth-aware reduction from ASP to SATthat adhere to the above limit

Project Head Stefan Woltran:
START