The power of counting and exponential sums

Abstract

We first study the concept of "Combinatorial Interpretations", i.e. the question of which quantities "count something". We start by showing that counting using finite automata is precisely closed under functions that ultimately are polynomial on residue classes and sums/products thereof. Following this, we show that graph motif parameters f(G) = Σ_i α_i #Ind(H_i -> G), where all pattern graphs H_i are without isolated vertices, can be counted by nondeterministic Turing machines in a local way exactly when all coefficients α_i are non-negative integers. The result is then generalized to other forms of subobject counts such as more general relational structures, colored graphs, finite vector spaces over finite fields, and parameter sets using category theory. Secondly, we study the complexity theoretic impact of adding unary summation primitives to the existential theory of the reals. We observe an exponential jump in complexity when the summation variables are allowed to be used to index variables, thus allowing for an exponential number of variables. This jump is characterized by the machine model of nondeterministic real word RAMs using exponential time, versus the polynomial time required for the standard existential theory of the reals. However, if the summation variables cannot be used for variable indexing, then we only observe NP_real^(VNP_ℝ)-completeness. It is thus likely a weaker model than the additional models compressing the input formula that we investigate: both an additional unary product primitive and a succinct encoding allowing only for polynomially many variables each lead to PSPACE-completeness. Next, we add unary summation primitives to the logic for reasoning about probabilities introduced by Fagin et al. -- extended by Ibeling and Icard to reason about Pearl's causal hierarchy. We fully investigate the changing landscape of complexity classes, depending on the arithmetic power of the terms, the level of the causal hierarchy, and varying constraints on the model. Many of these variations form natural complete problems for the complexity classes we observe by augmenting the existential theory of the reals. Lastly, we study the complexity of the identification problem on linear structural causal models. We are both interested in the complexity of numerically determining the parameters of the model uniquely, given the covariance matrix of the random variables, and the complexity of the generic problem of determining, for a given causal diagram, whether it is possible to reconstruct the parameters uniquely in almost all cases.

Wir betrachten zuerst das Konzept der "kombinatorischen Interpretierbarkeit", d.h. die Frage, welche Größen "etwas zählen". Wir beginnen damit zu zeigen, dass Zählen mithilfe von endlichen Automaten abgeschlossen ist unter genau solchen Funktionen, die letztendlich PORC-Funktionen sind und Summen/Produkte davon. Anschließend zeigen wir, dass Graph Motif Parameter f(G) = Σ_i α_i #Ind(H_i -> G), bei denen alle Mustergraphen H_i frei von isolierten Knoten sind, von einer nichtdeterministischen Turingmaschine genau dann lokal gezählt werden können, wenn alle Koeffizienten α_i nicht-negative Ganzzahlen sind. Dieses Ergebnis verallgemeinert sich zu anderen Arten von Subobjekten wie allgemeinen relationalen Strukturen, gefärbten Graphen, endlichen Vektorräumen über endlichen Körpern und Parametermengen durch die Verwendung von Kategorientheorie. Des Weiteren studieren wir den komplexitätstheoretischen Einfluss eines unären Summensymbols, zuerst zur existenziellen Theorie der reellen Zahlen. Wir beobachten einen exponentiellen Sprung in der Komplexität, wenn die Summationsvariablen verwendet werden dürfen, um Variablen zu indizieren, was eine Verwendung von exponentiell vielen Variablen erlaubt. Dieser Sprung lässt sich charakterisieren durch das Maschinenmodell der nichtdeterministischen reellen Wort-RAM mit exponentieller Zeit im Vergleich zur polynomiellen Zeit, die für die normale existenzielle Theorie der reellen Zahlen nötig ist. Falls jedoch die Summationsvariablen nicht zum Indizieren von Variablen verwendet werden dürfen, dann erhalten wir NP_real^(VNP_ℝ)-Vollständigkeit. Es handelt sich daher wahrscheinlich um ein schwächeres Modell als die anderen Kompressionsarten, die wir betrachten: ein unäres Produktsymbol, sowie kompakte Kodierungen, bei denen nur polynomiell viele Variablen verwendet werden dürfen, führen beide zu PSPACE-Vollständigkeit. Als nächstes fügen wir das Summensymbol in die Logik zum Schlussfolgern über Wahrscheinlichkeiten von Fagin et al. -- erweitert von Ibeling und Icard für Pearls kausale Hierarchie -- ein. Wir analysieren die Landschaft der Komplexitätsklassen, die sich durch verschieden starke Arithmetik, die kausale Ebene und verschiedener Beschränkungen des Modells ergibt, vollständig. Viele dieser Variationen formen natürliche vollständige Probleme für die Komplexitätsklassen, die wir auch durch unsere Veränderungen der existenziellen Theorie der reellen Zahlen beobachten. Zuletzt betrachten wir die Komplexität des Identifikationsproblems auf linearen strukturellen Kausalmodellen. Wir interessieren uns sowohl für die Komplexität, um, gegeben die Kovarianzmatrix der Zufallsvariablen, numerisch die Parameter des Modells eindeutig zu bestimmen, als auch die Komplexität, um zu entscheiden, gegeben ein kausales Diagramm, ob sich die Parameter in fast allen Fällen eindeutig rekonstruieren lassen.