Grenzen effizienter Verfahren

Die Komplexitätstheorie untersucht, ob ein Problem überhaupt lösbar ist und mit welchem Aufwand. Damit liefert dieser Kernbereich der Theoretischen Informatik anderen Teildisziplinen innerhalb der Informatik wichtige Hinweise, wo eine Suche nach effizienten Lösungen sinnvoll ist.

Die Einordnung in Problemklassen ist aber auch für praktische Anwendungen von Wert, beispielsweise für die Entwicklung von Texteditoren, von Datenkompressionslösungen oder für die Optimierung von Suchmaschinen.

Zur Einordnung von Problemen in unterschiedliche Klassen zieht die Komplexitätstheorie verschiedene Ressourcen heran. Beispielsweise geht es um die Frage, ob sich ein Problem mit den vorhandenen Rechenkapazitäten in einer realistischen Laufzeit lösen lässt. Der Aufwand für die Lösung steigt verständlicherweise mit der Größe der Eingabe, nur ist häufig nicht bekannt, welcher Aufwand wirklich geleistet werden muss.

Die Komplexitätstheorie hat in den vergangenen Jahren neue Ansätze und Methoden hervorgebracht. Diesen Fortschritt wollen sich die Trierer Informatiker um Professor Henning Fernau in ihrem Projekt zunutze machen und ihn auf den Bereich der formalen Sprachen anwenden.

Dabei handelt es sich um ein Gebiet, das unter anderem Mathematik, Linguistik oder auch Logik mit der Informatik verbindet. Sie sind auch Grundlage von Programmiersprachen.

„Die meisten Fragestellungen zu formalen Sprachen wurden unserem Empfinden nach weitgehend vernachlässigt, als in der letzten Dekade viele neue komplexitätstheoretische Konzepte entwickelt wurden“, erklärt Henning Fernau den Ansatz des von ihm geleiteten Forschungsvorhabens.

In einem Kick-Off-Workshop unter Leitung von Henning Fernau haben im Februar internationale Wissenschaftler aus vier Kontinenten gemeinsam nach neuen Strategien gesucht. „Es war ein sehr kreativer Prozess, in dem wir uns aus dem Blickwinkel eines Bereiches den Problemen eines anderen Bereichs genähert haben“, fasst Fernau die Herangehensweise zusammen.

Impulse aus dem mehrtägigen Workshop werden die Trierer Wissenschaftler in ihre Forschungsarbeit aufnehmen, in der Hoffnung, in der dreijährigen Laufzeit des von der Deutschen Forschungsgemeinschaft geförderten Projektes entweder bessere Verfahren zu finden oder nachweisen zu können, dass es diese nicht geben kann. Die auf der Basis von theoretischen Methoden gewonnenen Ergebnisse dürften auch Anwender, Programmierer und Wissenschaftler in Informatik-Nachbardisziplinen interessieren bzw. ihnen zugutekommen.

Prof. Dr. Henning Fernau
Theoretische Informatik
Tel. +49 651-201 2827
E-Mail: fernau@uni-trier.de