Loading…
New Classes of Complete Problems for the Second Level of the Polynomial Hierarchy
Johannes, Berit
Eine wichtige Aufgabe der diskreten Mathematik besteht in der Kategorisierung von kombinatorischen Optimierungsproblemen nach ihrem Schwierigkeitsgrad. Die grundlegendsten und bekanntesten Komplexitätsklassen sind zweifelsohne P und NP. Auf P und NP baut sich die polynomielle Hierarchie auf, die aus vielen weiteren Komplexitätsklassen besteht, deren Probleme schwerer zu sein scheinen als die Probleme in P und NP. Die Komplexitätsklasse ∑2p liegt in dieser Hierarchie eine Stufe über NP und enthält all die Probleme, die durch einen nichtdeterministischen Algorithmus mit Hilfe eines NP-Orakels gelöst werden können. Im Gegensatz zu den Klassen P und NP erfreut sich die Klasse ∑2p geringerer Bekanntheit, was unter anderem daran liegen mag, dass sie naturgemäss komplizierter ist, und man bisher nur wenige natürliche Probleme kennt, die bezüglich dieser Klasse vollständig sind. Der Hauptbeitrag der vorliegenden Arbeit liegt in der Entwicklung einer neuen Methode, die es erlaubt, ganze Klassen von Problemen, die in ∑2p liegen, als ∑2p-vollständig zu beweisen. Diese Technik benutzt bestimmte Eigenschaften bestehender Transformationen zwischen NP-vollständigen Problemen, um eine polynomielle Transformation von einem ∑2p-vollständigen Problem zu einer in ∑2p liegenden Variante eines anderen Problems zu erzeugen. Damit zeigt diese Arbeit nicht nur neue, durchaus natürliche und grundlegende, ∑2p-vollständige Probleme auf, sondern steuert ganze Familien von Problemen bei, die ∑2p-vollständig sind. Zu dieser Art von Problemen gehören Varianten von in 0-1 Variablen formulierbaren Zulässigkeitsproblemen, bei denen man fragt, ob es für eine vorgegebene Teilmenge der Variablen eine 0-1 Zuweisung gibt, so dass für die restlichen Variablen keine 0-1 Belegung mehr möglich ist, die zu einer insgesamt zulässigen Lösung führen würde. Eine andere Klasse von Problemen betrifft Situationen, in denen die Zielfunktion vorerst nur in einem gewissen Rahmen vorgegeben ist. Dann geht es darum, die Instanz vor der eigentlichen Lösung des Problems zu verkleinern, indem man für einzelne Variablenbelegungen testet, ob sie überhaupt Teil einer optimalen Lösung sein können. Eine weitere Klasse von ∑2p-vollständigen Problemen ergibt sich aus Fragen nach der Existenz von Gegenbeispielen für Vermutungen im Zusammenhang mit NP-schweren Problemen. Ein Beispiel hierzu ist die Frage, ob eine Vermutung falsch ist, die besagt, dass alle Graphen mit einer bestimmten Eigenschaft einen Hamiltonischen Kreis haben. Zusätzliche Probleme und Problemklassen, die in dieser Arbeit als ∑2p-vollständig bewiesen werden, betreffen Fragestellungen wie den Versuch, eine beschränkte Anzahl der Variablen so zu belegen, dass es genau eine zulässige Erweiterung dazu gibt, oder die Aufgabe herauszufinden, ob ein gegebenes ganzzahliges Optimierungsproblem überflüssige Ungleichungen enthält.
An important aspect of discrete optimization is to analyze the computational complexity of combinatorial optimization problems. The polynomial hierarchy provides a proper classification scheme for decision problems that appear to be harder than NP-complete. With P and NP at the bottom of the polynomial hierarchy, the next most interesting class is arguably ∑2p, which is the central topic of this thesis. The complexity class ∑2p lies one level above the class NP and contains all decision problems that can be solved efficiently by a nondeterministic algorithm that has access to an NP oracle. In contrast to the complexity classes P and NP, the class ∑2p has not yet attracted much attention, since it is inherently more intricate than the other classes and, on top of that, it has suffered from a scarcity of natural complete problems. The main contribution of this thesis is the development of a new and powerful tool that uses established transformations between NP-complete problems to prove ∑2p-completeness for entire classes of problems. We show how and under which circumstances a polynomial time transformation from one NP-complete problem P1 to another NP-complete problem P2 can be used to derive a polynomial time transformation from an established ∑2p-complete problem corresponding to P1 to a version of P2 in ∑2p, which is then, as a consequence, ∑2p-complete as well. As a result, we will provide many families of complete problems for ∑2p, most of which are quite natural, some even basic. This list of problems includes adversarial problems, which ask whether there is a 0-1 assignment to a specified subset of the variables so that it is not possible to complete this assignment to a feasible solution, no matter which values are assigned to the remaining variables. Another class concerns preprocessing problems. Given an instance of a combinatorial optimization problem with some flexibility for the objective function, we ask whether there exists an objective function such that a particular element becomes part of an optimal solution. We also establish that it is ∑2p-complete to decide whether there exists a counterexample to an NP-conjecture. An example of such a problem would be the question whether a graph with a certain property is Hamiltonian or not. More problems that are shown to be ∑2p-complete include defining set problems, which ask whether for a given instance of a decision problem there is a partial solution of a certain size that can be completed to a feasible solution in a unique way, and the problem of deciding whether a given integer program has redundant constraints.
