TY  - THES
A3  - Bürgisser, Peter
A3  - Meyer auf der Heide, Friedhelm
A3  - Segoufin, Luc
AB  - 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.
AU  - Mengel, Stefan
DA  - 2013
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 18.07.2013
N1  - Paderborn, Univ., Diss., 2013
PB  - Veröffentlichungen der Universität
PY  - 2013
T2  - Institut für Mathematik
TI  - Conjunctive queries, arithmetic circuits and counting complexity
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-11944
Y2  - 2026-01-20T22:49:55
ER  -