Project Details
Projekt Print View

Duality in Circuit Complexity

Applicant Professor Dr. Klaus-Jörn Lange, since 2/2018
Subject Area Theoretical Computer Science
Term from 2018 to 2021
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 395094066
 
Final Report Year 2021

Final Report Abstract

Das eigentliche Gebiet des Forschungsvorhabens ist die Komplexitätstheorie, die geprägt ist von offenen Fragen und ungelösten Problemen. Die Mehrzahl der wenigen Erfolge betreffen den unteren Komplexitätsbereich, meist in Form von Schaltkreisklassen konstanter Tiefe. Die Fortschritte dort gehen einher mit einem engen Zusammenspiel von Methoden aus Algebra und Topologie und ergaben engste Zusammenhänge mit formalen Sprachen. Allerdings beschränkt sich dies auf formalsprachlicher Seite auf den Bereich der regulären Sprachen, also endlicher Monoide. Es gibt zwar Ansätze auch kontextfreie Sprachen derart zu untersuchen, die aber nicht die algebraische oder gar topologische Maschinerie nutzbar machten. Ziel dieses Forschungsvorhabens war es daher, diese erfolgreiche Zusammenarbeit von Algebra und Topologie auch außerhalb des Bereichs der regulären Sprachen und damit auch außerhalb von Schaltkreisklassen konstanter Tiefe auszunutzen. Ein erstes Untersuchungsgebiet bildeten daher die Visibly Pushdown Sprachen, die zum Einen NC 1-vollständig sind, und damit anscheinend nicht mehr durch Schaltkreise konstanter Tiefe erkennbar sind, und zum Anderen hinsichtlich ihrer Eigenschaften den regulären Sprachen noch sehr ähnlich sind. So unterschiedlich die Gebiete der formalen Sprachen und der Komplexitätstheorie auch sind, so gibt es doch als verbindendes Element die Beschreibung durch Prädikatenlogik erster Stufe für den Bereich der Schaltkreise konstanter Tiefe und der regulären Sprachen. Diese Beschreibung war hilfreich bei der Zerlegung mathematischer Konstrukte entlang der Schaltkreistiefe, die mit der Tiefe der entsprechenden Quantorverschachtelung übereinstimmt, in (semidirekte) Produkte von Substitutionen, von Transformationen oder von atomaren Bausteinen. Die Untersuchung dieses Wechselspiels verschiedener mathematischer Werkzeugsätze noch ohne konkreten Anwendungsbezug war auch Anliegen des Vorhabens. Als eine zusätzliche Fragerichtung, die schon bei der Antragstellung implizit im Raume stand, ergab sich aus dem extremen Unterschied der Zugänglichkeit der beiden Gebiete Formale Sprachen und Komplexität trotz ihrer inhaltlichen Nähe die Frage nach einer formalen Charakterisierung des Begriffs einer Familie formaler Sprachen, da sich über diesen Begriff Ansätze für die Unterscheidung von Determinismus und Nichtdeterminismus zu ergeben scheinen.

Publications

 
 

Additional Information

Textvergrößerung und Kontrastanpassung