Details

Autor(en) / Beteiligte

• Mengel, Stefan
• Bürgisser, Peter
• Meyer auf der Heide, Friedhelm
• Segoufin, Luc

Titel

Conjunctive queries, arithmetic circuits and counting complexity [Elektronische Ressource]

Erscheinungsjahr

2013

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)
• Volltext

  kostenfrei

Link zu anderen Inhalten

• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 18.07.2013
• Paderborn, Univ., Diss., 2013
• Open Access
• ger: In dieser Arbeit geht es um verschiedene Themen aus der Zählkomplexität und der arithmetischen Schaltkreiskomplexität.Der erste Teil untersucht die Komplexität des Zählens der Antworten auf Conjunctive Queries, eine grundlegende Klasse von Anfragen aus der Datenbanktheorie. Wir führen den Parameter quantified star size einer Query phi ein, der misst, wie die freien Variablen in phi verteilt sind. Wir ordnen der Query phi einen Hypergraphen zu und zeigen, dass für Klassen von Queries mit beschränkter generalized hypertree width der Parameter quantified star size genau die Unterklassen charakterisiert, für die das Zählen von Antworten effizient möglich ist. Wir charakterisieren im Fall beschränkter Arität die Klassen von Conjunctive Queries, für die effizientes Zählen von Antworten möglich ist, vollständig. Weiterhin betrachten wir auch die Kompexität der Berechnung der quantified star size von Conjunctive Queries.Im zweiten Teil charakterisieren wir unterschiedliche Klassen aus der arithmetischen Schaltkreiskomplexität auf verschiedene Arten, durch Conjunctive Queries, durch Graphpolynome auf Graphen beschränkter Baumweite und durch eine Erweiterung des klassischen Modells der arithmetischen Branchingprogramme durch Stack-Speicher. Insbesondere zeigen wir neue Charakterisierungen der arithmetischen Schaltkreisklasse VP, einer Klasse, die zentral für den Bereich ist aber nicht gut verstanden.Der dritte Teil beschäftigt sich mit zwei Entscheidungproblemen zu Polynomen gegeben durch arithmetische Schaltkreise: Testen ob ein gegebenes Monom vorkommt und Zählen der vorkommenden Monome. Wir zeigen, dass diese Probleme vollständig sind für unterschiedliche Levels der sogenannten counting hierarchy, für die bisher wenige oder keine natürlichen vollständigen Probleme bekannt waren.
• eng: This thesis deals with several subjects from counting complexity and arithmetic circuit complexity.The first part explores the complexity of counting solutions to conjunctive queries, which are a basic class of queries from database theory. We introduce a parameter, called the quantified star size of a query phi, which measures how the free variables are spread in phi. As usual in database theory, we associate a hypergraph to a query phi. We show that for classes of queries for which these associated hypergraphs have bounded generalized hypertree width, bounded quantified star size exactly characterizes the subclasses of queries for which counting the number of solutions is tractable. In the case of bounded arity, this allows us to fully characterize the classes of conjunctive queries for which counting the solutions is tractable. Finally, we also analyze the complexity of computing the quantified star size of a conjunctive query.In the second part we characterize different classes from arithmetic circuit complexity by different means, including conjunctive queries and constraint satisfaction problems, graph polynomials on bounded treewidth graphs, and an extension of the classical arithmetic branching program model by stack memory.In particular, this yields new characterizations of the arithmetic circuit class VP, a class that is central to the area but arguably not well understood.Finally, the third part studies the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of its monomials. We show that these problems are complete for different levels of the counting hierarchy, which had few or no known natural complete problems before.