Prof. Dr. Martin Grohe

• Die Struktur parametrischer Komplexitätsklassen (I)

  Quelle ↗

  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, dass 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 betrachte 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.

• Die Komplexität von Constraint-Satisfaction Problemen (I)

  Quelle ↗

  <p>Constraint-Satisfaction-Probleme (CSP) bilden eine natürliche Klasse von algorithmischen Problemen, die wichtige Anwendungen in ganz verschiedenen Bereichen wie künstliche Intelligenz, Datenbanken, automatische Verifikation und statistische Physik haben. Prominentestes Beispiel eines CSP, das auch in diesem Projekt eine wichtige Rolle spielen soll, ist das aussagenlogische Erfüllbarkeitsproblem.</p><p>Es ist seit langem bekannt, dass CSP im Allgemeinen NP-vollständig und damit, zumindest theoretisch, nicht effizient lösbar sind. In der Praxis hat es in den letzten Jahren jedoch enorme Fortschritte bei der Lösung insbesondere des aussagenlogischen Erfüllbarkeitsproblems gegeben. Inzwischen werden in industriellen Anwendungen Instanzen mit mehr als 10.000 Variablen routinemäßig gelöst.</p><p>Es liegt hier also eine deutliche Diskrepanz zwischen den theoretischen "worst-case" Vorhersagen und der Praxis vor. Als Grund für diese Diskrepanz wird oft genannt, dass in der Praxis auftretende Instanzen "strukturiert" sind. Allerdings ist es völlig unklar, welche strukturellen Eigenschaften hier relevant sind und wie diese von den üblicherweise eingesetzten Algorithmen ausgenützt werden. Diese Fragen sollen im Mittelpunkt des Projekts stehen. Neben CSP und SAT als zentralem Beispiel soll hier auch eine Reihe verwandter Probleme, etwa Zählprobleme, untersucht werden.</p>

• Die Struktur parametrischer Komplexitätsklassen (II)

  Quelle ↗

  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, dass 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 betrachte 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.

Noch keine Publikationen aus OpenAlex zugeordnet.