Untersuchungen Arithmetischer und Boole'scher Komplexität von Schaltkreisen kleiner Tiefe

• Antragsteller: Professor Dr. Heribert Vollmer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 270077289

• Erstellungsjahr: 2021

Zusammenfassung der Projektergebnisse

Arithmetische Schaltkreise bilden ein in letzter Zeit viel untersuchtes Rechenmodell in der theoretischen Informatik als theoretische Basis für Komplexitätsuntersuchungen von numerischen Algorithmen, beispielsweise zur Berechnung von Problemen über Polynomen, Problemen der linearen Algebra, etc. Die Popularität des Modells rührt daher, dass es sich um ein sehr eingeschränktes („strukturiertes“) Berechnungsmodell in dem Sinne handelt, dass es nur über einen sehr begrenzten Satz von Operationen verfügt, die es verwenden kann (es kann nicht auf die binare Darstellung berechneter Werte zugreifen). Dies ist der Hauptgrund, warum viele bemerkenswerte Ergebnisse zur Komplexität grundlegender mathematischer Funktionen und viele tiefliegende untere Komplexitätsschranken bekannt sind. Es gibt eine interessante Verbindung zwischen Boole’schen Schaltkreisen und einer bestimmten Art von arithmetischen Schaltkreisen über den natürlichen Zahlen mit den Operationen Addition, Multiplikation und evtl. weiteren Operationen. Der Ausgabewert eines arithmetischen Schaltkreises findet sich im zugehörigen Boole’schen Schaltkreis in der Anzahl der sog. „Beweisbäume“, das sind minimale Teilschaltkreise, die beweisen, dass der Schaltkreis insgesamt seine Eingabe akzeptiert. Wir haben also eine Verbindung zwischen arithmetischen Berechnungen und Zahlproblemen in Boole’schen Schaltkreisen vorliegen. Ziel dieses Projektes war es, Komplexitätsklassen, die über arithmetische Schaltkreise definiert sind, auf verschiedene Weisen zu charakterisieren, nämlich - modelltheoretisch, also mit Mitteln der mathematischen Logik, indem die Arbeitsweise von Schaltkreisen durch Formeln beschrieben wird; dieses Gebiet ist auch als „deskriptive Komplexität“ bekannt, - rekursionstheoretisch, also mit Mitteln der universellen Algebra, indem die relevanten Komplexitätsklassen sich als Abschluss gewisser elementarer Funktionen unter Substitution und verschiedenen Formen von Rekursion ergeben. Für die wichtigsten Schaltkreisklassen kleiner Tiefe, also #AC0, #NC1, #SAC1 und #AC1, ist beides gelungen. Die Verbindung zu Boole’schen Schaltkreisen war einerseits ein Hilfsmittel in den Beweisen, andererseits ergeben sich rückwirkend nun auch Konsequenzen und neuartige Charakterisierungen von Boole’schen Klassen. Wir hoffen, dass durch die erreichten Charakterisierungen nun eine neue Toolbox zur Untersuchung der Mächtigkeit arithmetischer Schaltkreise zur Verfügung steht, weil möglicherweise Methoden der Logik und universellen Algebra in der Komplexitätstheorie genutzt werden können. Im Verlaufe des Projekts ergab sich überraschenderweise eine enge Verbindung von sog. „team-basierten Logiken“ und Schaltkreisen über den reellen Zahlen, die in Zukunft weiter untersucht werden soll.

Projektbezogene Publikationen (Auswahl)

• “A model-theoretic characterization of constant-depth arithmetic circuits,” in Logic, Language, Information, and Computation - 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016. Proceedings (J. A. Vä äanänen, A. Hirvonen, and R. J. G. B. de Queiroz, eds.), vol. 9803 of Lecture Notes in Computer Science, pp. 234–248, Springer, 2016
  A. Haak and H. Vollmer
  
• “Descriptive complexity of #AC0 functions,” in 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France (J. Talbot and L. Regnier, eds.), vol. 62 of LIPIcs, pp. 20:1–20:16, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2016
  A. Durand, A. Haak, J. Kontinen, and H. Vollmer
  
• “Model-theoretic characterization of boolean and arithmetic circuit classes of small depth,” in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018 (A. Dawar and E. Grädel, eds.), pp. 354–363, ACM, 2018
  A. Durand, A. Haak, and H. Vollmer
  
• “A model-theoretic characterization of constant-depth arithmetic circuits,” Ann. Pure Appl. Log., vol. 170, no. 9, pp. 1008–1029, 2019
  A. Haak and H. Vollmer
  
• “Counting of teams in first-order team logics,” in 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany (P. Rossmanith, P. Heggernes, and J. Katoen, eds.), vol. 138 of LIPIcs, pp. 19:1–19:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019
  A. Haak, J. Kontinen, F. Müller, H. Vollmer, and F. Yang
  
• “A logical characterization of constant-depth circuits over the reals.” in: Proceedings of WoLLIC, Springer LNCS, 2021
  T. Barlag and H. Vollmer
  
• “Descriptive complexity of #P functions: A new perspective,” J. Comput. Syst. Sci., vol. 116, pp. 40–54, 2021
  A. Durand, A. Haak, J. Kontinen, and H. Vollmer