Schwerpunkte

In der Komplexitätstheorie wird die Berechnungskomplexität von Problemen in verschiedenen Berechnungsmodellen untersucht. Typische Modelle sind die Turing-Maschine, Random-Access-Maschinen und Boole'sche (oder arithmetische) Schaltkreise. Auf diesen werden dann gewisse Komplexitätstmaße definiert, bei Turing-Maschinen sind die gängigsten beispielsweise Laufzeit und Speicherbedarf. Probleme werden dann auf Basis der benötigten Ressourcen zur algorithmischen Lösung des Problems klassifiziert. In diesem Zusammenhang wird versucht, sowohl obere als auch untere Schranken für die Mitgliedschaft von Problemen in solchen Klassen zu zeigen. Die genauere Untersuchung oberer Schranken, insbesondere auch in Hinblick auf eine feinere Einordnung, wird meist der Algorithmik zugeordnet. Für unsere Forschungsschwerpunkte ist es sinnvoll, Teilgebiete der Komplexitätstheorie anhand folgender Kriterien zu definieren:

• Art der Probleme: Entscheidungsprobleme (gibt es eine Lösung?), Zählprobleme (wie viele Lösungen gibt es?), Enumerationsprobleme (Aufzählung aller Lösungen), etc.
  
• Berechnungsmodell: Turing-Maschine, Random-Access-Maschine, Boole'sche (oder arithmetische) Schaltkreise, etc.
• Exaktheit der Lösung: exakte Lösung, Approximation, Berechnung nur auf gewisse Eingaben effizient (parametrisierte Komplexität), etc.

Neben diesen eher problembezogenen Fragestellungen werden in der Komplexitätstheorie auch strukturelle Eigenschaften von Komplexitätsklassen untersucht, um diese besser zu verstehen. Beispielsweise können Abschlusseigenschaften dieser Klassen gezeigt werden, bei Klassen von Entscheidungsproblemen beispielsweise der Abschluss unter Boole'schen Operationen.

In der mathematischen Logik werden verschiedenste logische Formalismen untersucht.

Neben den sehr bekannten Vertretern wie der Prädikatenlogik und Aussagenlogik werden von uns verschiedene Team-Logiken sowie nichtklassische Logiken, vornehmlich die Default-Logik, untersucht. Die Besonderheit bei Team-Logiken ist die Betrachtung von Belegungsmengen, sogenannten Teams, anstelle von einzelnen Belegungen. Diese können in gewissem Sinne als Datenbankinstanzen verstanden werden und es ist dann möglich wichtige Konzepte aus dem Bereich der Datenbanken in diesen Logiken auszudrücken.

Dabei widmen wir uns insbesondere Fragen zur Berechnungskomplexität von gewissen Problemen, zum Beispiel dem Erfüllbarkeitsproblem oder Modelchecking, in den einzelnen Logiken.

Ein Teilgebiet, das genau im Schnittbereich der Komplexitätstheorie und Logik angesiedelt ist, ist die deskriptive Komplexität. Hier wird versucht Logiken zu finden, in denen sich exakt die Probleme aus einer bestimmten Komplexitätsklasse definieren lassen.

Die Feinstruktur von Komplexitätsklassen, die über Schaltkreise kleiner Tiefe definiert sind (also NC¹, SAC¹ und Teilklassen) soll untersucht werden. Dabei soll insbesondere auf Mittel aus der Logik (Beschreibungskomplexität und Theorie endlicher Modelle) und Algebra (Gruppoidtheorie und algebraische Automatentheorie) zurückgegriffen werden.

Sogenannte Enumerationsprobleme befassen sich mit der Aufzählung (engl. enumeration) aller Lösungen. Wir untersuchen die Komplexität solcher Aufzählprobleme und messen hierbei die Verzögerung (engl. delay), die Zeit zwischen der Ausgabe von zwei Lösungen. Der Ursprung dieses Forschungsbereiches geht auf eine Arbeit von Johnson, Papadimitriou und Yannakakis (On Generating All Maximal Independent Sets. Inf. Process. Lett. 27(3): 119-123 (1988)) zurück.

Im letzten Jahrzehnt wuchs das Forschungsgebiet der Enumerationsalgorithmen enorm, was auf die stetig zunehmende Datenmenge, die die Algorithmen im Alltag verarbeiten müssen, zurückzuführen ist. Die Hauptanwendung stellt sicherlich die Abfrage einer Datenbank dar, wobei eine große Menge an Daten verarbeitet werden muss. Deshalb ist die inkrementelle und effiziente Berechnung der Anfragen ein immer wichtiger werdendes Thema. So möchten zum Beispiel die Nutzer einer Web-Suchmaschine möglichst schnell eine Antwort auf eine Schlüsselwortabfrage bekommen. Des Weiteren findet die Enumeration in den Gebieten Operation Research, Data Mining, Bioinformatik, Computerlinguistik, sowie bei der Lösung von Constraints Anwendung.

Eine der zentralen Erkenntnisse der Komplexitätstheorie ist die Schwere gewisser Probleme: So ist für die Lösung von Problemen wie dem Erfüllbarkeitsproblem der Aussagenlogik kein Algorithmus mit subexponentieller Laufzeit bekannt. Die meisten Experten gehen davon aus, dass es einen solchen nicht gibt. In der Praxis sehen sich jedoch viele Menschen mit Problemen, die in einem solchen Sinne als schwierig klassifiziert wurden, konfrontiert und letztlich können diese in vielen Anwendungsbereichen in annehmbarer Zeit gelöst werden.

Es gibt nun verschiedene Ansätze, um zu verstehen wie es zu dieser anscheinenden Diskrepanz zwischen theoretischen Ergebnissen und der Situation in der Praxis kommt. Einer dieser Ansätze untersucht die  parametrisierte Komplexität: Hier werden Probleme betrachtet, bei denen eine quantifizierbare strukturelle Eigenschaft der Eingabe als getrennter Parameter ausgezeichnet wird. Es wird dann die Komplexität in Abhängigkeit der gesamten Eingabegröße und dieses Parameters analysiert.

Es werden hierbei Komplexitätsklassen definiert, bei denen die Laufzeit in Abhängigkeit des Parameters deutlich stärker wachsen kann als in Abhängigkeit der Eingabegröße. So wird ein parametrisiertes Problem beispielsweise als effizient lösbar angesehen, wenn die benötigte Laufzeit das Produkt aus einem Polynom in der Eingabegröße und einer beliebigen berechenbaren Funktion im Parameter ist. Das heißt, dass die Laufzeit abhängig vom Parameter fast beliebig stark wachsen kann, allerdings für feste Parameterwerte durch ein festes Polynom beschränkt ist.

Das Ziel ist letztlich, Parameter zu finden, die in der Praxis häufig sehr klein bleiben. Ist das Problem mit einem solchen Parameter effizient lösbar, so liefert dieses in gewissem Rahmen eine Erklärung für die Handhabbarkeit in der Praxis.

Die deskriptive Komplexität befasst sich auf struktureller Ebene mit den Eigenschaften von Komplexitätsklassen. Es wird versucht, Logiken anzugeben, in denen sich exakt die Probleme definieren lassen, die in eine bestimmte Komplexitätsklasse fallen. Neben eigenständigem Interesse an solchen Charakterisierungen besteht auch die Hoffnung, durch Methoden der Logik damit weitere Erkenntnisse zu den Eigenschaften der charakterisierten Komplexitätsklasse zu gewinnen.

Team-Semantik wurde 1997 von Wilfrid Hodges eingeführt, um die spieltheoretische Semantik von Logiken mit unvollständiger Information durch eine kompositionale Semantik abzulösen, wie sie für viele Logiken üblich ist. Im Unterschied zur gewöhnlichen Tarski-Semantik werden Formeln dabei nicht mehr mit einzelnen Belegungen ausgewertet, sondern mit Mengen von Belegungen, genannt Teams.

Darauf aufbauend führte Jouko Väänänen 2007 seine Dependence Logic ein, die die Prädikatenlogik um das Abhängigkeitsatom =(x,y) ergänzt. Dieses sagt intuitiv aus, das im gesamten Team der Wert der Variable y eindeutig durch x bestimmt wird. Es stellte sich heraus, dass dies sogar erlaubt, Aussagen der Prädikatenlogik zweiter Stufe zu formulieren. Seitdem wurden viele weitere nichtklassische Atome eingeführt, um Aussagen über die Abhängigkeit und Unabhängigkeit von Belegungen innerhalb eines Teams zu formalisieren.

Wir untersuchen Team-Logik vor allem in Hinblick auf die Berechnungskomplexität, Ausdrucksstärke und Axiomatisierbarkeit und betrachten dabei auch aussagenlogische, modallogische und temporallogische Varianten.

Das Erfüllbarkeitsproblem, also das Berechnungsproblem, von einer gegebenen aussagenlogischen Formel zu entscheiden, ob sie erfüllbar ist, ist das klassische NP-vollständige Problem, dessen Studium die Entwicklung der Komplexitätstheorie in nicht zu unterschätzendem Ausmaß geprägt hat. Bekannterweise erlauben eingeschränkte Formelklassen effiziente Entscheidungsalgorithmen, z. B. Horn-Formeln. In diesem Schwerpunkt soll die Grenze zwischen algorithmischer Nicht-Handhabbarkeit und effizienter Lösbarkeit für Erfüllbarkeitsprobleme und verwandte algorithmische Fragestellungen in verschiedenen logischen Formalismen unter besonderer Berücksichtigung einer möglichst genauen komplexitätstheoretischen Klassifizierung der effizienten Fälle genau bestimmt werden, etwa im Hinblick auf Speicherbedarf oder Parallelisierbarkeit.

Einen besonderen Schwerpunkt bei unseren Untersuchungen sollen so genannte nichtmonotone Logiken einnehmen, die Verwendung vor allem in Bereichen wie Wissensrepräsentation, Semantic Web, Expertensysteme, etc. finden.

Methodisch sollen die Untersuchungen auf Mittel der universellen Algebra, insbesondere den Post'schen Verband abgeschlossener Klassen von Boole'schen Funktionen, zurückgreifen.