Till innehåll på sidan

Johannes Klaus Fichte: Parameterized complexity of answer set programming

Tid: Må 2017-11-27 kl 12.00

Plats: Room 4523, Lindstedtsvägen 5, KTH CSC 

Medverkande: Johannes Klaus Fichte, Technische Universität Wien

Exportera till kalender

PRACTICALITIES

Lunch is served at 12:00 noon (register at this doodle  at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

In this talk, we consider answer set programming (ASP) and its parameterized complexity.

ASP is a logic-based declarative modeling and problem solving framework, in which many important problems of artificial intelligence and reasoning can be succinctly represented. It has been applied to several large applications such as optimization of packaging of Linux distributions.

Although the main problems of propositional disjunctive ASP are of high computational complexity, located at the second level of the polynomial hierarchy, several restrictions of ASP have been identified, under which ASP problems become tractable. A variety of these restrictions originate in parameterized complexity. A key concept in parameterized complexity is fixed-parameter tractability, which relaxes classical polynomial-time tractability in such a way that all non-polynomial parts depend only on the size of the parameter and not on the size of the input.

We present two frameworks, which allow us to establish fixed-parameter tractability, namely, backdoors and treewidth. Backdoors are small sets of atoms that represent "clever reasoning shortcuts" through the search space allowing for efficient evaluation of computational problems in ASP. Treewidth roughly measures to which extent the internal structure of a program resembles a tree. We design treewidth-based algorithms, which run in linear time if the treewidth and weights of the given program are bounded.

Due to an increasing practical interest in efficient solving and the situation that most state-of-the-art ASP solvers generally rely on CDCL-based solving, an important research question is whether such algorithms can be built into solvers that are competitive with established solvers. To this end, we present a new implementation of our treewidth based algorithms.