Detlef Seese
Complexity in theory and application structural and descriptive aspects

Detlef Seese, Karlsruhe Institute of Technology, Germany

Abstract:

Many algorithmic problems interesting from a theoretical or practical point of view are *NP*-hard and permit at least till now no efficient algorithmic solution. Usually one tries to get solutions in polynomial time by restricting structural parameters of the input structures (e.g. as in parameterized complexity considering structures of bounded width - band-width, tree-width, branch-width, path-width, …) or restricting the language allowed for problem definition (descriptive complexity).

In the talk we consider a unified combinatorial / logical approach to demonstrate that many complexity results in this area can be deduced using tools developed for the investigation of the decidability and undecidability of theories in mathematical logic.

The approach shows where areas of special interest for further research are located. Moreover areas of potential applications will be discussed.

Imprint Privacy policy « This page (revision-4) was last updated on Thursday, 6. October 2011, 11:25 by Kaiser Dana
  • operated by