Dualität und Schaltkreiskomplexität

• Antragsteller: Professor Dr. Klaus-Jörn Lange, seit 2/2018
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 395094066

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 letzten 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 begründete Dualität wurde bereits erfolgreich in der Logik angewandt: Zum Beispiel von Abramsky im Bereich der Programmlogik und der 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. In keiner dieser integrierte sich die algebraische Komponente so gut wie im regulären Fall. Durch die Untersuchung stark beschränkter Komplexitätsklassen, gewannen wir eine Idee, wie eine allgemeine Methode, unter Zuhilfenahme eines erweiterten Dreiklanges, für Trennungsergebnisse funktionieren könnte.Das Ziel unseres Forschungsvorhabens 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 Topologie 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 Trennungsergebnisse und erweitern diese Schritt für Schritt auf größere Schaltkreisklassen.Der dritte Bereich 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.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Privatdozent Dr. Andreas Krebs, bis 2/2018