New Classes of Complete Problems for the Second Level of the Polynomial Hierarchy [Elektronische Ressource] / Berit Johannes. Betreuer: James B. Orlin

New Classes of Complete Problemsfor the Second Level of the Polynomial Hierarchyvorgelegt vonDipl.-Math. oec. Berit JohannesVon der Fakult¨at II – Mathematik und Naturwissenschaftender Technischen Universit¨at Berlinzur Erlangung des akademischen GradesDoktor der Naturwissenschaften– Dr. rer. nat. –genehmigte DissertationBerichter: Prof. Dr. James B. OrlinProf. Dr. Rolf H. M¨ohringVorsitzender: Prof. Dr. Fredi Tr¨oltzschTag der wissenschaftlichen Aussprache: 27. Juni 2011Berlin 2011D 833ZusammenfassungEine wichtige Aufgabe der diskreten Mathematik besteht in der Kategorisierungvon kombinatorischen Optimierungsproblemen nach ihrem Schwierigkeitsgrad. Diegrundlegendsten und bekanntesten Komplexit¨atsklassen sind zweifelsohne P und NP.AufPundNPbautsichdiepolynomielleHierarchieauf,dieausvielenweiterenKom-plexit¨atsklassen besteht, deren Probleme schwerer zu sein scheinen als die Problemepin P und NP. Die Komplexit¨atsklasse Σ liegt in dieser Hierarchie eine Stufe u¨ber NP2undenth¨altalldieProbleme, diedurcheinennichtdeterministischenAlgorithmusmitHilfe eines NP-Orakels gel¨ost werden k¨onnen. Im Gegensatz zu den Klassen P undpNPerfreutsichdieKlasseΣ geringererBekanntheit,wasunteranderemdaranliegen2mag, dass sie naturgem¨ass komplizierter ist, und man bisher nur wenige natu¨rlicheProbleme kennt, die bezu¨glich dieser Klasse vollst¨andig sind.