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

• Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy. LATA 2018: 156-168
  Demen Güler, Andreas Krebs, Klaus-Jörn Lange, Petra Wolf
  
• Visibly Pushdown Languages and Free Profinite Algebras. CoRR abs/1810.12731 (2018)
  Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange
  
• Wreath Products of Distributive Forest Algebras. LICS 2018: 512-520
  Michael Hahn, Andreas Krebs, Howard Straubing
  
• A topological approach to non-uniform complexity. Inf. Comput. 269 (2019)
  Silke Czarnetzki, Andreas Krebs
  
• Skew circuits of small width. Theor. Comput. Sci. 821: 111-123 (2020)
  Nikhil Balaji, Andreas Krebs, Nutan Limaye: