Theoretical Tractability vs. Practical Computation

01.09.2008 - 31.08.2012
Research funding project
Over the past years, we have been experiencing a rapid progress of business process automation and a pervasion of virtually all aspects of life by computers. Consequently, computational solutions are needed for increasingly hard problems in a great variety of fields. However, the intractability (i.e., NP-completeness or even higher complexity) of many important problems is a strong obstacle to the design of efficient solutions. Two major lines of research have been pursued in response to this situation: ¿ Parameterized complexity and the study of fixed-parameter algorithms have evolved as a very active research area and a lot of progress has been made in identifying tractable fragments of many hard problems. However, a theoretical tractability result as such does, in general, not automatically yield a computer program which actually runs efficiently in practice. ¿ Powerful tools have been making enormous progress in solving even intractable problems, among them most notably SAT solvers and datalog systems like DLV. Of course, we cannot expect these tools to cope with any real-world instances of an intractable problem. But they do perform reasonably well in many cases. However, a typical shortcoming of these tools is that, in general, they do not take advantage of tractable fragments of hard problems, i.e., although a problem instance falls into a theoretically easy subclass, the resources needed for solving it are essentially the same as with really hard problem instances. The primary goal of the proposed project is to combine the power of strong theoretical tractability results with the power of the advanced software tool DLV in order to allow for an efficient solution of many practically relevant problems. The key to this combination of theory and practice is an efficient fragment of datalog, which has recently been proposed for tackling a big class of problems with tractable fragments. We want to further pursue this method in order to make progress concerning the following three objectives of the project: 1. On the system side, we aim at an enhancement of DLV by making theoretical tractability results accessible to it. 2. On the theory side, we look for novel tractability results. 3. On the application side, we plan the development of algorithms for many (tractable fragments of) hard problems in a great variety of fields.

People

Project leader

Project personnel

Institute

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Research focus

  • Computational Intelligence: 100%

Keywords

GermanEnglish
Parameterized ComplexityParameterized Complexity
Fixed-parameter TractabilityFixed-parameter Tractability
Tree-widthTree-width
DatalogDatalog
Monadic Second-order logicMonadic Second-order logic

External partner

  • Oxford University Computing Laboratory
  • Universita degli Studi di Calabria

Publications