Johannes Klaus Fichte, Martin Kronegger, Stefan Woltran,
"A Multiparametric View on Answer Set Programming"
, in Bart Bogaerts , Amelia Harrison: Proceedings of the 10th Workshop on Answer Set Programming and Other Computing Paradigms co-located with the 14th International Conference on Logic Programming and Nonmonotonic Reasoning, ASPOCP@LPNMR, Serie CEUR Workshop Proceedings, Vol. 1868, CEUR, 7-2017
Original Titel:
A Multiparametric View on Answer Set Programming
Sprache des Titels:
Englisch
Original Buchtitel:
Proceedings of the 10th Workshop on Answer Set Programming and Other Computing Paradigms co-located with the 14th International Conference on Logic Programming and Nonmonotonic Reasoning, ASPOCP@LPNMR
Original Kurzfassung:
Disjunctive answer set programming (ASP) is an important
framework for declarative modeling and problem solving, where the computational
complexity of basic decision problems like consistency (deciding
whether a program has an answer set) is located on the second level of
the polynomial hierarchy. During the last decades different approaches
have been applied to find tractable fragments of programs, in particular,
also using parameterized complexity. However, the full potential of
parameterized complexity has not been unlocked since only one or very
few parameters have been considered at once. In this paper, we consider
several natural parameters for the consistency problem of disjunctive
ASP. In addition, we also take the size of the answer set into account; a
restriction that is particularly interesting for applications requiring small
solutions. Previous work on parameterizing the consistency problem by
the size of answer sets yielded mostly negative results. In contrast, we
start from recent findings for the problem WMMSAT and show several
novel fixed-parameter tractability (fpt) results based on combinations of
parameters. Moreover, we establish a variety of hardness results (paraNP,
W[2], and W[1]-hardness) to assess tightness of our combined parameters.