This thesis is devoted to the study of computational complexity theory, a branch of theoretical computer science. Computational complexity theory investigates the inherent difficulty in designing efficient algorithms for computational problems. By doing so, it analyses the scalability of computational problems and algorithms and places practical limits on what computers can actually accomplish. Computational problems are categorised into complexity classes. Among the most important complexity classes are the class NP and the subclass of NP-complete problems, which comprises many important optimisation problems in the field of operations research. Moreover, with the P-NP-problem, the class NP represents the most important unsolved question in computer science. The first part of this thesis is devoted to the study of NP-complete-, and more generally, NP-hard problems. It aims at improving our understanding of this important complexity class by systematically studying how altering NP-hard sets affects their NP-hardness. This research is related to longstanding open questions concerning the complexity of unions of disjoint NP-complete sets, and the existence of sparse NP-hard sets. The second part of the thesis is also dedicated to complexity classes but takes a different perspective: In a sense, after investigating the interior of complexity classes in the first part, the focus shifts to the description of complexity classes and thereby to the exterior in the second part. It deals with the description of complexity classes through leaf languages, a uniform framework which allows us to characterise a great variety of important complexity classes. The known concepts are complemented by a new leaf-language model. To a certain extent, this new approach combines the advantages of the known models. The presented results give evidence that the connection between the theory of formal languages and computational complexity theory might be closer than formerly known. / Diese Dissertation behandelt die Komplexitätstheorie, ein zentrales Teilgebiet der Theoretischen Informatik. Die Komplexitätstheorie untersucht die inhärente Schwierigkeit, effiziente Algorithmen für Berechnungsprobleme zu entwerfen. Sie analysiert die Skalierbarkeit von Berechnungsproblemen und Algorithmen und stellt grundsätzliche Grenzen für die Leistungsfähigkeit von Computern auf. Berechnungsprobleme werden in Komplexitätsklassen kategorisiert. Dabei spielen die Klasse NP und die in ihr enthaltene Klasse der NP-vollständigen Probleme eine wichtige Rolle. Letztere umfasst zahlreiche in der Praxis bedeutsame Probleme aus dem Bereich Operations Research. Darüber hinaus repräsentiert die Klasse NP mit dem P-NP Problem gleichfalls das wichtigste ungelöste Problem in der Informatik. Der erste Teil dieser Dissertation ist der Untersuchung NP-vollständiger und noch allgemeiner, NP-harter Mengen gewidmet. Durch eine systematische Untersuchung der Frage, wie sich partielle Modifikationen von Mengen auf deren NP-Härte auswirken, soll das Verständnis dieser wichtigen Komplexitätsklasse verbessert werden. Die Untersuchungen in diesem Bereich stehen in enger Verbindung zu wichtigen ungelösten Fragen, wie beispielsweise der Frage nach der Komplexität von Vereinigungen disjunkter NP-vollständiger Mengen und darüber hinaus der Frage nach der Existenz dünner, NP-harter Mengen. Der zweite Teil der Dissertation beschäftigt sich ebenfalls mit der Komplexitätstheorie, nimmt dabei aber eine andere Perspektive ein: Während im ersten Teil mit der Untersuchung struktureller Eigenschaften innere Aspekte von Komplexitätsklassen im Vordergrund stehen dreht es sich im zweiten Teil um die Beschreibung von Komplexitätsklassen. Dabei werden so genannte Blattsprachen verwendet, welche einen uniformen Beschreibungsmechanismus für Komplexitätsklassen darstellen. Die bestehenden Blattsprachen-Konzepte werden durch einen neuen Ansatz ergänzt, der in einem gewissen Sinne die Vorteile der bekannten Ansätze vereint. Die erzielten Ergebnisse sind Evidenz dafür, dass die Verbindung zwischen der Theorie der formalen Sprachen und der Komplexitätstheorie noch enger ist als bislang vermutet.

This thesis is divided into two parts. In the first part we contribute to a working program initiated by Pudlák (2017) who lists several major complexity theoretic conjectures relevant to proof complexity and asks for oracles that separate pairs of corresponding relativized conjectures. Among these conjectures are: - \(\mathsf{CON}\) and \(\mathsf{SAT}\): coNP (resp., NP) does not contain complete sets that have P-optimal proof systems. - \(\mathsf{CON}^{\mathsf{N}}\): coNP does not contain complete sets that have optimal proof systems. - \(\mathsf{TFNP}\): there do not exist complete total polynomial search problems (also known as total NP search problems). - \(\mathsf{DisjNP}\) and \(\mathsf{DisjCoNP}\): There do not exist complete disjoint NP pairs (coNP pairs). - \(\mathsf{UP}\): UP does not contain complete problems. - \(\mathsf{NP}\cap\mathsf{coNP}\): \(\mathrm{NP}\cap\mathrm{coNP}\) does not contain complete problems. - \(\mathrm{P}\ne\mathrm{NP}\). We construct several of the oracles that Pudlák asks for. In the second part we investigate the computational complexity of balance problems for \(\{-,\cdot\}\)-circuits computing finite sets of natural numbers (note that \(-\) denotes the set difference). These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al. (2010). Our work shows that the balance problem for \(\{-,\cdot\}\)-circuits is undecidable which is the first natural problem for integer circuits or related constraint satisfaction problems that admits only one arithmetic operation and is proven to be undecidable. Starting from this result we precisely characterize the complexity of balance problems for proper subsets of \(\{-,\cdot\}\). These problems turn out to be complete for one of the classes L, NL, and NP. / Diese Arbeit gliedert sich in zwei Teile. Im ersten Teil liefern wir Beiträge zu einem Arbeitsprogramm, das von Pudlák (2017) initiiert wurde, welcher einige bedeutsame komplexitätstheoretische, für das Gebiet der Proof Complexity relevante Vermutungen untersucht und nach Orakeln fragt, die Paare von entsprechenden relativierten Vermutungen separieren. Unter diesen Vermutungen sind: - \(\mathsf{CON}\) und \(\mathsf{SAT}\): coNP (resp., NP) enthält keine vollständigen Probleme, die P-optimale Beweissysteme haben. - \(\mathsf{CON}^{\mathsf{N}}\): coNP enthält keine vollständigen Probleme, die optimale Beweissysteme haben. - \(\mathsf{TFNP}\): Es existieren keine vollständigen Total Polynomial Search Problems (auch bekannt unter dem Namen Total NP Search Problems). - \(\mathsf{DisjNP}\) und \(\mathsf{DisjCoNP}\): Es gibt keine vollständigen disjunkten NP-Paare (coNP-Paare). - \(\mathsf{UP}\): UP enthält keine vollständigen Probleme. - \(\mathsf{NP}\cap\mathsf{coNP}\): \(\mathrm{NP}\cap\mathrm{coNP}\) enthält keine vollständigen Probleme. - \(\mathrm{P}\ne\mathrm{NP}\) Wir konstruieren einige der Orakel, nach denen Pudlák fragt. Im zweiten Teil untersuchen wir die Berechnungskomplexität von Balance Problemen für \(\{-,\cdot\}\)-Schaltkreise, welche endliche Teilmengen natürlicher Zahlen berechnen (es bezeichnet \(-\) die Differenz von Mengen). Diese Probleme bauen in natürlicher Weise auf Probleme für Integer Expressions und Integer Circuits auf, welche von Stockmeyer und Meyer (1973), McKenzie und Wagner (2007) sowie Glaßer et al. (2010) untersucht wurden. Wir beweisen, dass das Balance Problem für \(\{-,\cdot\}\)-Schaltkreise unentscheidbar ist. Dies ist das erste natürliche Problem für Integer Circuits oder verwandte Constraint Satisfaction Probleme, das nur eine arithmetische Operation erlaubt und als unentscheidbar bewiesen worden ist. Von diesem Resultat ausgehend wird die Komplexität von Balance Problemen für echte Teilmengen von \(\{-,\cdot\}\) präzise charakterisiert. Es stellt sich heraus, dass jedes dieser Probleme vollständig für eine der Klassen L, NL und NP ist.