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.
| Identifer | oai:union.ndltd.org:uni-wuerzburg.de/oai:opus.bibliothek.uni-wuerzburg.de:2319 |
| Date | January 2007 |
| Creators | Travers, Stephen |
| Source Sets | University of Würzburg |
| Language | English |
| Detected Language | English |
| Type | doctoralthesis, doc-type:doctoralThesis |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0118 seconds