Die Struktur parametrischer Komplexitätsklassen

• Antragsteller: Professor Dr. Jörg Flum; Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2003 bis 2012
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5416593

Die Komplexitätstheorie macht Aussagen über die zur Lösung von algorithmischen Problemen erforderlichen Ressourcen, wie etwa Rechenzeit. Dabei wird die Komplexität eines Problems üblicherweise als Funktion der Eingabegröße gemessen. Dieses einfache Modell führt zu einer klaren Einteilung in Klassen von leicht und schwer lösbaren algorithmischen Problemen, hat aber den Nachteil, daß gewisse feinere Strukturen der Eingabe nicht berücksichtigt und unter Umständen Probleme als "schwer" klassifiziert werden, obwohl nur gewisse für die Praxis irrelevante Fälle schwer lösbar sind. Häufig besteht die Eingabe eines Problems aus mehreren Teilen. Als Beispiel betrachtet man das Problem, eine Datenbankanfrage auszuwerten. Die Eingabe besteht hier aus der Anfrage und der Datenbank. Normalerweise ist die Datenbank um ein Vielfaches größer als die Anfrage. Die parametrische Komplexitätstheorie berücksichtigt dies und ermöglicht eine verfeinerte Komplexitätsanalyse. Ziel des Projektes ist es, ein klareres Bild der noch sehr unübersichtlichen Struktur der parametrischen Komplexitätsklassen und ihres Verhältnisses zu klassischen Klassen zu erlangen. Eine systematische Untersuchung der "Parameterabhängigkeit" von Problemen soll eine realistischere Einschätzung ihrer Komplexität ermöglichen, als dies bisher möglich ist.

• DFG-Verfahren: Sachbeihilfen