Arithmetic versus Boolean Complexity: The Case of Small-Depth Circuits
Final Report Abstract
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.
Publications
- “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
(See online at https://doi.org/10.1007/978-3-662-52921-8_15) - “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
(See online at https://doi.org/10.4230/LIPIcs.CSL.2016.20) - “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
(See online at https://doi.org/10.1145/3209108.3209179) - “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
(See online at https://doi.org/10.1016/j.apal.2019.04.006) - “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
(See online at https://doi.org/10.4230/LIPIcs.MFCS.2019.19) - “A logical characterization of constant-depth circuits over the reals.” in: Proceedings of WoLLIC, Springer LNCS, 2021
T. Barlag and H. Vollmer
(See online at https://doi.org/10.1007/978-3-030-88853-4_2) - “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
(See online at https://doi.org/10.1016/j.jcss.2020.04.002)
