We use algebraic closures and structures which are derived from these in complexity theory. We classify problems with Boolean circuits and Boolean constraints according to their complexity. We transfer algebraic structures to structural complexity. We use the generation problem to classify important complexity classes. / Algebraische Hüllen und Strukturen, die mit solchen zusammenhängen, werden für die Komplexitätstheorie genutzt. Es werden Probleme im Zusammenhang mit Booleschen Schaltkreisen und Constraint-Satisfaction Problemen komplexitätstheoretisch klassifiziert. Strukturen aus der Algebra werden auf die Strukturelle Komplexität übertragen. Das Generierungsproblem, wird zur Klassifikation wichtiger Komplexitätsklassen benutzt.

Motivated by results on interactive proof systems we investigate the computational power of quantifiers applied to well-known complexity classes. In special, we are interested in existential, universal and probabilistic bounded error quantifiers ranging over words and sets of words, i.e. oracles if we think in a Turing machine model. In addition to the standard oracle access mechanism, we also consider quantifiers ranging over oracles to which access is restricted in a certain way. / Angeregt durch die Resultate über interaktive Beweissysteme untersuchen wir Quantoren in Anwendung auf bereits bekannte Komplexitätsklassen hinsichtlich ihrer dadurch gegebenen Berechnungsmächtigkeit. Von besonderem Interesse sind dabei existentielle und universelle Quantoren sowie Quantoren mit begrenzter Fehlerwahrscheinlichkeit, die alle über Wörter oder Wortmengen (Orakel im Kontext der Turingmaschinen) quantifizieren. Außer in Bezug auf den Standardmechanismus eines Orakelzugriffs werden auch Quantifizierungen über Orakel, für deren Zugriff gewisse Beschränkungen bestehen, betrachtet.

The first part of this thesis deals with the approximability of the traveling salesman problem. This problem is defined on a complete graph with edge weights, and the task is to find a Hamiltonian cycle of minimum weight that visits each vertex exactly once. We study the most important multiobjective variants of this problem. In the multiobjective case, the edge weights are vectors of natural numbers with one component for each objective, and since weight vectors are typically incomparable, the optimal Hamiltonian cycle does not exist. Instead we consider the Pareto set, which consists of those Hamiltonian cycles that are not dominated by some other, strictly better Hamiltonian cycles. The central goal in multiobjective optimization and in the first part of this thesis in particular is the approximation of such Pareto sets. We first develop improved approximation algorithms for the two-objective metric traveling salesman problem on multigraphs and for related Hamiltonian path problems that are inspired by the single-objective Christofides' heuristic. We further show arguments indicating that our algorithms are difficult to improve. Furthermore we consider multiobjective maximization versions of the traveling salesman problem, where the task is to find Hamiltonian cycles with high weight in each objective. We generalize single-objective techniques to the multiobjective case, where we first compute a cycle cover with high weight and then remove an edge with low weight in each cycle. Since weight vectors are often incomparable, the choice of the edges of low weight is non-trivial. We develop a general lemma that solves this problem and enables us to generalize the single-objective maximization algorithms to the multiobjective case. We obtain improved, randomized approximation algorithms for the multiobjective maximization variants of the traveling salesman problem. We conclude the first part by developing deterministic algorithms for these problems. The second part of this thesis deals with redundancy properties of complete sets. We call a set autoreducible if for every input instance x we can efficiently compute some y that is different from x but that has the same membership to the set. If the set can be split into two equivalent parts, then it is called weakly mitotic, and if the splitting is obtained by an efficiently decidable separator set, then it is called mitotic. For different reducibility notions and complexity classes, we analyze how redundant its complete sets are. Previous research in this field concentrates on polynomial-time computable reducibility notions. The main contribution of this part of the thesis is a systematic study of the redundancy properties of complete sets for typical complexity classes and reducibility notions that are computable in logarithmic space. We use different techniques to show autoreducibility and mitoticity that depend on the size of the complexity class and the strength of the reducibility notion considered. For small complexity classes such as NL and P we use self-reducible, complete sets to show that all complete sets are autoreducible. For large complexity classes such as PSPACE and EXP we apply diagonalization methods to show that all complete sets are even mitotic. For intermediate complexity classes such as NP and the remaining levels of the polynomial-time hierarchy we establish autoreducibility of complete sets by locally checking computational transcripts. In many cases we can show autoreducibility of complete sets, while mitoticity is not known to hold. We conclude the second part by showing that in some cases, autoreducibility of complete sets at least implies weak mitoticity. / Der erste Teil dieser Arbeit widmet sich der Approximierbarkeit des Traveling Salesman Problems, bei welchem man in vollständigen Graphen mit Kantengewichten eine Rundreise mit minimalem Gewicht sucht. Es werden die wichtigsten mehrkriteriellen Varianten dieses Problems betrachtet, bei denen die Kantengewichte aus Vektoren natürlicher Zahlen mit einer Komponente pro Kriterium bestehen. Verschiedene Rundreisen sind bei mehrkriteriellen Kantengewichten häufig unvergleichbar, und dementsprechend existiert oft keine eindeutige optimale Rundreise. Stattdessen fasst man jene Rundreisen, zu denen jeweils keine eindeutig bessere Rundreise existiert, zu der sogenannten Pareto-Menge zusammen. Die Approximation solcher Pareto-Mengen ist die zentrale Aufgabe in der mehrkriteriellen Optimierung und in diesem Teil der Arbeit. Durch Techniken, die sich an Christofides' Heuristik aus der einkriteriellen Approximation orientieren, werden zunächst verbesserte Approximationsalgorithmen für das zweikriterielle metrische Traveling Salesman Problem auf Multigraphen und für analog definierte Hamiltonpfadprobleme entwickelt. Außerdem werden Argumente gegen eine signifikante Verbesserung dieser Algorithmen aufgezeigt. Weiterhin werden mehrkriterielle Maximierungsvarianten des Traveling Salesman Problems betrachtet, bei denen man Rundreisen mit möglichst großem Gewicht in jedem Kriterium sucht. Es werden einkriterielle Techniken auf den mehrkriteriellen Fall übertragen, bei denen man zunächst eine Kreisüberdeckung mit hohem Gewicht berechnet und anschließend pro Kreis die Kante mit dem niedrigsten Gewicht löscht. Die Auswahl einer solchen Kante pro Kreis ist im mehrkriteriellen Fall nicht trivial, weil mehrkriterielle Gewichtsvektoren häufig unvergleichbar sind. Es wird ein allgemeines Lemma entwickelt, welches dieses Problem löst und damit eine Übertragung der einkriteriellen Maximierungsalgorithmen auf den mehrkriteriellen Fall ermöglicht. Dadurch ergeben sich verbesserte, randomisierte Approximationsalgorithmen für die mehrkriteriellen Maximierungsvarianten des Traveling Salesman Problems. Abschließend werden zu diesen Problemvarianten deterministische Algorithmen entwickelt. Der zweite Teil dieser Arbeit widmet sich Redundanzeigenschaften vollständiger Mengen. Eine Menge heißt autoreduzierbar, wenn zu jeder Instanz x eine von x verschiedene Instanz y mit der gleichen Zugehörigkeit zu der Menge effizient berechnet werden kann. Ist die Menge in zwei äquivalente Teile aufspaltbar, so heißt sie schwach mitotisch, und ist diese Aufspaltung durch einen effizient entscheidbaren Separator erreichbar, so heißt sie mitotisch. Zu verschiedenen Reduktionen und Komplexitätsklassen wird die Frage betrachtet, wie redundant ihre vollständigen Mengen sind. Während sich vorherige Forschung in diesem Gebiet hauptsächlich auf Polynomialzeitreduktionen konzentriert, liefert diese Arbeit eine systematische Analyse der Redundanzeigenschaften vollständiger Mengen für typische Komplexitätsklassen und solche Reduktionen, die sich in logarithmischem Raum berechnen lassen. Je nach Größe der Komplexitätsklasse und Stärke der Reduktion werden dabei verschiedene Techniken eingesetzt. Für kleine Komplexitätsklassen wie beispielsweise NL und P werden selbstreduzierbare, vollständige Mengen benutzt, um Autoreduzierbarkeit aller vollständigen Mengen nachzuweisen, während für große Komplexitätsklassen wie beispielsweise PSPACE und EXP Diagonalisierungsmethoden sogar die Mitotizität vollständiger Mengen zeigen. Für dazwischen liegende Komplexitätsklassen wie beispielsweise NP und die übrigen Level der Polynomialzeithierarchie wird Autoreduzierbarkeit vollständiger Mengen über lokales Testen von Berechnungstranskripten gezeigt. Während in vielen Fällen Autoreduzierbarkeit vollständiger Mengen gezeigt werden kann, bleibt häufig die Frage offen, ob diese Mengen auch mitotisch sind. Abschließend wird gezeigt, dass in einigen Fällen Autoreduzierbarkeit vollständiger Mengen zumindest schwache Mitotizität impliziert.

In der klassischen Komplexitätstheorie unterscheiden wir zwischen der Klasse P von in Polynomialzeit lösbaren Problemen, und der Klasse NP-schwer von Problemen bei denen die allgemeine Annahme ist, dass diese nicht in Polynomialzeit lösbar sind. Allerdings sind viele Probleme, die wir lösen möchten, NP-schwer. Gleichzeitig besteht eine große Diskrepanz zwischen den empirisch beobachteten und den festgestellten worst-case Laufzeiten. Es ist bekannt, dass Vorverarbeitung oder Datenreduktion auf realen Instanzen zu Laufzeitverbesserungen führt. Hier stoßen wir an die Grenze der klassischen Komplexitätstheorie. Der Fokus dieser Arbeit liegt auf Vorverarbeitungsalgorithmen für NP-schwere Probleme. Unser Ziel ist es, bestimmte Instanzen eines NP-schweren Problems vorverarbeiten zu können, indem wir die Struktur betrachten. Genauer gesagt, für eine gegebene Instanz und einen zusätzlichen Parameter l, möchten wir in Polynomialzeit eine äquivalente Instanz berechnen, deren Größe und Parameterwert nur durch eine Funktion im Parameterwert l beschränkt ist. In der parametrisierten Komplexitätstheorie heißen diese Algorithmen Kernelisierung. Wir werden drei NP-schwere Graphenprobleme betrachten, nämlich Vertex Cover, Edge Dominating Set und Subset Feedback Vertex Set. Für Vertex Cover werden wir bekannte Ergebnisse für Kernelisierungen vereinheitlichen, wenn der Parameter die Größe einer Entfernungsmenge zu einer gegebenen Graphklasse ist. Anschließend untersuchen wir die Kernelisierbarkeit von Edge Dominating Set. Es stellt sich heraus, dass die Kernelisierbarkeit deutlich komplexer ist. Dennoch klassifizieren wir die Existenz einer polynomiellen Kernelisierung, wenn jeder Graph in der Graphklasse eine disjunkte Vereinigung von konstant großen Komponenten ist. Schließlich betrachten wir das Subset Feedback Vertex Set Problem und zeigen, dass es eine randomisierte polynomielle Kernelisierung hat, wenn der Parameter die Lösungsgröße ist. / In classical complexity theory, we distinguish between the class P, of polynomial-time solvable problems, and the class NP-hard, of problems where the widely-held belief is that we cannot solve these problems in polynomial time. Unfortunately, many of the problems we want to solve are NP-hard. At the same time, there is a large discrepancy between the empirically observed running times and the established worst-case bounds. Using preprocessing or data reductions on real-world instances is known to lead to huge improvements in the running time. Here we come to the limits of classical complexity theory. In this thesis, we focus on preprocessing algorithms for NP-hard problems. Our goal is to find ways to preprocess certain instances of an NP-hard problem by considering the structure of the input instance. More precisely, given an instance and an additional parameter l, we want to compute in polynomial time an equivalent instance whose size and parameter value is bounded by a function in the parameter l only. In the field of parameterized complexity, these algorithms are called kernelizations. We will consider three NP-hard graph problems, namely Vertex Cover, Edge Dominating Set, and Subset Feedback Vertex Set. For Vertex Cover, we will unify known results for kernelizations when parameterized by the size of a deletion set to a specified graph class. Afterwards, we study the existence of polynomial kernelizations for Edge Dominating Set when parameterized by the size of a deletion set to a graph class. We point out that the existence of polynomial kernelizations is much more complicated than for Vertex Cover. Nevertheless, we fully classify the existence of polynomial kernelizations when every graph in the graph class is a disjoint union of constant size components. Finally, we consider graph cut problems, especially the Subset Feedback Vertex Set problem. We show that this problem has a randomized polynomial kernelization when the parameter is the solution size.

The importance of family involvement is highlighted by findings that parents’ behaviours, beliefs and attitudes affect children’s behaviour in a major way. The Family Maths programme, which is the focus of this study, provides support for the transformative education practices targeted by the South African Department of Education by offering an intervention which includes teachers, learners and their families in an affirming learning community. In this study participating parents were interviewed to investigate their perceptions of the Family Maths programme mainly in terms of their engagement, enjoyment and confidence levels. The major themes and ideas that were generated in this study include the development of positive attitudes, parents and children working and talking together, and the skills exhibited by Family Maths facilitators. These findings are analysed within the parameters of complexity science and the pre-requisite conditions for developing a complex learning community, viz. internal diversity, redundancy, decentralized control, organised randomness and neighbour interactions.

The importance of family involvement is highlighted by findings that parents’ behaviours, beliefs and attitudes affect children’s behaviour in a major way. The Family Maths programme, which is the focus of this study, provides support for the transformative education practices targeted by the South African Department of Education by offering an intervention which includes teachers, learners and their families in an affirming learning community. In this study participating parents were interviewed to investigate their perceptions of the Family Maths programme mainly in terms of their engagement, enjoyment and confidence levels. The major themes and ideas that were generated in this study include the development of positive attitudes, parents and children working and talking together, and the skills exhibited by Family Maths facilitators. These findings are analysed within the parameters of complexity science and the pre-requisite conditions for developing a complex learning community, viz. internal diversity, redundancy, decentralized control, organised randomness and neighbour interactions.

Die Theorie disjunkter NP-Paare, die auf natürliche Weise statt einzelner Sprachen Paare von NP-Mengen zum Objekt ihres Studiums macht, ist vor allem wegen ihrer Anwendungen in der Kryptografie und Beweistheorie interessant. Im Zentrum dieser Dissertation steht die Analyse der Beziehung zwischen disjunkten NP-Paaren und aussagenlogischen Beweissystemen. Haben die Anwendungen der NP-Paare in der Beweistheorie maßgeblich das Verständnis aussagenlogischer Beweissysteme gefördert, so beschreiten wir in dieser Arbeit gewissermaßen den umgekehrten Weg, indem wir Methoden der Beweistheorie zur genaueren Untersuchung des Verbands disjunkter NP-Paare heranziehen. Insbesondere ordnen wir jedem Beweissystem P eine Klasse DNPP(P) von NP-Paaren zu, deren Disjunktheit in dem Beweissystem P mit polynomiell langen Beweisen gezeigt werden kann. Zu diesen Klassen DNPP(P) zeigen wir eine Reihe von Resultaten, die illustrieren, dass robust definierten Beweissystemen sinnvolle Komplexitätsklassen DNPP(P) entsprechen. Als wichtiges Hilfsmittel zur Untersuchung aussagenlogischer Beweissysteme und der daraus abgeleiteten Klassen von NP-Paaren benutzen wir die Korrespondenz starker Beweissysteme zu erststufigen arithmetischen Theorien, die gemeinhin unter dem Schlagwort beschränkte Arithmetik zusammengefasst werden. In der Praxis trifft man statt auf zwei häufig auf eine größere Zahl konkurrierender Bedingungen. Daher widmen wir uns der Erweiterung der Theorie disjunkter NP-Paare auf disjunkte Tupel von NP-Mengen. Unser Hauptergebnis in diesem Bereich besteht in der Charakterisierung der Fragen nach der Existenz optimaler Beweissysteme und vollständiger NP-Paare mit Hilfe disjunkter Tupel. / Disjoint NP-pairs are an interesting complexity theoretic concept with important applications in cryptography and propositional proof complexity. In this dissertation we explore the connection between disjoint NP-pairs and propositional proof complexity. This connection is fruitful for both fields. Various disjoint NP-pairs have been associated with propositional proof systems which characterize important properties of these systems, yielding applications to areas such as automated theorem proving. Further, conditional and unconditional lower bounds for the separation of disjoint NP-pairs can be translated to results on lower bounds to the length of propositional proofs. In this way disjoint NP-pairs have substantially contributed to the understanding of propositional proof systems. Conversely, this dissertation aims to transfer proof-theoretic knowledge to the theory of NP-pairs to gain a more detailed understanding of the structure of the class of disjoint NP-pairs and in particular of the NP-pairs defined from propositional proof systems. For a proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make the previously defined canonical NP-pairs of these proof systems hard or complete for DNPP(P). Moreover, we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for DNPP(P) and the reductions between the canonical pairs exist. As an important tool for our investigation we use the connection of propositional proof systems and disjoint NP-pairs to theories of bounded arithmetic.

Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist. / This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.

Partitionierung von Graphen ist im Allgemeinen sehr schwierig. Es stehen derzeit keine Algorithmen zur Verfügung, die ein allgemeines Partitionierungsproblem effizient lösen. Aus diesem Grund werden heuristische Ansätze verfolgt. Zur Analyse dieser Heuristiken ist man derzeit gezwungen zufällige Graphen zu Verwenden. Daten realer Graphen sind derzeit entweder nur sehr schwer zu erheben (z.B. Internetgraph), oder aus rechtlichen bzw. wirtschaftlichen Gründen nicht zugänglich (z.B. soziale Netzwerke). Die untersuchten Heuristiken liefern teilweise nur unter bestimmten Voraussetzungen Ergebnisse. Einige arbeiten lediglich auf einer eingeschränkten Menge von Graphen, andere benötigen zum Erkennen einer Partition einen mit der Knotenzahl steigenden Durchschnittsgrad der Knoten, z.B. [DHM04]. Der im Zuge dieser Arbeit erstmals implementierte Algorithmus aus [CGL07a] benötigt lediglich einen konstanten Durchschnittsgrad der Knoten um eine Partition des Graphen, wenn diese existiert, zu erkennen. Insbesondere muss dieser Durchschnittsgrad nicht mit der Knotenzahl steigen. Nach der Implementierung erfolgten Tests des Algorithmus an zufälligen Graphen. Diese Graphen entsprachen dem Gnp-Modell mit eingepflanzter Partition. Die untersuchten Clusterprobleme waren dabei große Schnitte, kleine Schnitte und unabhängige Mengen. Der von der Art des Clusterproblems abhängige Durchschnittsgrad wurde während der Tests bestimmt.

In an increasing number of use cases, databases face the challenge of managing irregularly structured data. Irregularly structured data is characterized by a quickly evolving variety of entities without a common set of attributes. These entities do not show enough regularity to be captured in a traditional database schema. A common solution is to centralize the diverse entities in a universal table. Usually, this leads to a very sparse table. Although today's techniques allow efficient storage of sparse universal tables, query efficiency is still a problem. Queries that reference only a subset of attributes have to read the whole universal table including many irrelevant entities. One possible solution is to use a partitioning of the table, which allows pruning partitions of irrelevant entities before they are touched. Creating and maintaining such a partitioning manually is very laborious or even infeasible, due to the enormous complexity. Thus an autonomous solution is desirable. In this paper, we define the Online Partitioning Problem for irregularly structured data and present Cinderella. Cinderella is an autonomous online algorithm for horizontal partitioning of irregularly structured entities in universal tables. It is designed to keep its overhead low by incrementally assigning entities to partitions while they are touched anyway during modifications. The achieved partitioning allows queries that retrieve only entities with a subset of attributes easily pruning partitions of irrelevant entities. Cinderella increases the locality of queries and reduces query execution cost.