Dualität und Schaltkreiskomplexität

01/04/2018 to 31/03/2021

Ein Hauptaugenmerk der Komplexitätstheorie ist die Trennung von Komplexitätsklassen. Die Grenze unseres Wissens liegt nicht zwischen P und NP, sondern innerhalb der konstant tiefen Schaltkreisklassen. Für viele Einzelfälle wurden dort Trennungsergebnisse gezeigt. Die hierfür verwendeten Methoden scheinen auf die jeweiligen Klassen zugeschnitten zu sein. Eine allgemeine Beweisstrategie fehlt uns bisher.

In den letzen Jahren fand ein neuer Ansatz Einzug in die Komplexitätstheorie, der auf eine einheitliche Beweisstrategie hoffen lässt. Dieser Ansatz beruht auf dem Darstellungssatz von Stone und ist in der Lage Komplexitätsklassen als topologische Räume zu interpretieren. Hierdurch werden topologische Methoden anwendbar. Da die Topologie ein etabliertes Feld der Mathematik ist, werden eine Vielzahl solcher Methoden zur Verfügung gestellt.

Die von Stone beründete Dualität wurde bereits erfolgreich in der Logik angewandt: Zum Beispiel von Abramsky im Bereich der Programmlogik und Domain Theorie und von Esakia, für die Definition einer Semantik in der intuitionistischen Logik.

Die Verbindung zwischen topologischen Objekten und Sprachklassen war für die regulären Sprachen bekannt, im Zusammenspiel mit einer dritten algebraischen Komponente. Dieser Dreiklang führte zu unzähligen Charakterisierungen und Trennungsergebnissen zwischen Unterklassen der regulären Sprachen.

Im Bezug auf Komplexitätsklassen, die weit außerhalb der regulären Sprachen liegen, gab es mehrere Ansätze eine algebraische Komponente hinzuzufügen, aber keine die sich ebenso integrierte, wie die algebraische Komponente im regulären Fall. Durch die Untersuchung stark beschränkter Komplexitätsklassen, gewannen wir eine Idee, wie eine allgemeine Methode für Trennungsergebnisse funktionieren könnte, unter Zuhilfenahme eines erweiterten Dreiklanges.

Das Ziel unseres Forschunsvorhabens ist daher die weitere Vertiefung des Dreiklangs zwischen Topologie, Komplexitätsklassen und Algebra. Wir teilen unser Vorhaben in drei Bereiche ein:
Der erste Bereich beschäftigt sich mit Unterklassen der Visibly Pushdown Sprachen. Diese weisen ähnlich gute Eigenschaften wie die regulären Sprachen auf und sind daher ein ideales Gebiet zur Vertiefung unseres Verständnisses, wie das Zusammenspiel von Topolpogie und Algebra zu Trennungsergebnissen beiträgt.
Im zweiten Bereich erforschen wir konstant tiefe Schaltkreisklassen. Insbesondere konzentrieren wir uns auf die Weiterentwicklung unserer allgemeinen Beweismethode für Trennungsergbenisse und erweitern diese Schritt für Schritt auf größere Schaltkreisklassen.
Der dritte Bereicht ist dem Aufbau der mathematischen Theorie gewidmet. Die in den ersten beiden bereichen angewandte Theorie verdient individuelle Betrachtung und es ist unser Ziel sie allgemein anwendbar zu machen.