Die Struktur parametrischer Komplexitätsklassen IV

Die parametrische Komplexitätstheorie ermöglicht eine verfeinerte Komplexitätsanalyse schwieriger algorithmischer Probleme. Bislang wurde vor allem die parametrische Komplexität von Entscheidungsproblemen auf deterministischen und nichtdeterministischen Maschinen analysiert und klassifiziert. Der erste Förderungsabschnitt dieses Projekts hat sich im Wesentlichen in diesem Rahmen bewegt.

In diesem Projekt wollen wir in zweierlei Hinsicht über diesen Rahmen hinausgehen. Erstens soll das Hauptaugenmerk nicht mehr auf Entscheidungsproblemen, sondern auf Optimierungs- und Zählproblemen liegen; eine wichtige Rolle werden dabei Approximierbarkeitsfragen spielen. Zweitens sollen allgemeinere Berechenbarkeitsmodelle betrachtet werden; zum einen wollen wir randomisierte Algorithmen (bzw. probabilistische Maschinen) in die parametrische Komplexitätstheorie einbinden und die Rolle des Zufalls untersuchen und zum anderen algebraische Berechenbarkeitsmodelle, insbesondere das BSS-Modell für Berechenbarkeit auf reellen Zahlen, betrachten.

All dies sind zentrale Themen der modernen Komplexitätstheorie, die allerdings in der parametrischen Theorie bisher noch keine große Rolle gespielt haben, weil dort zunächst noch grundlegendere Fragen zu klären waren.

Projektleitung
Grohe, Martin Prof. Dr. (Details) (Theoretische Informatik)

Mittelgeber
DFG: Sachbeihilfe

Laufzeit
Projektstart: 10/2009
Projektende: 07/2011

Zuletzt aktualisiert 2020-13-03 um 23:07