[{Image src='seese-detlef-2.jpg' caption='' width='500' alt='Detlef Seese' class='image_left'}]''__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.