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

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2011
• Nombre de lectures: 35
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

New Classes of Complete Problems
for the Second Level of the Polynomial Hierarchy
vorgelegt von
Dipl.-Math. oec. Berit Johannes
Von der Fakult¨at II – Mathematik und Naturwissenschaften
der Technischen Universit¨at Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
– Dr. rer. nat. –
genehmigte Dissertation
Berichter: Prof. Dr. James B. Orlin
Prof. Dr. Rolf H. M¨ohring
Vorsitzender: Prof. Dr. Fredi Tr¨oltzsch
Tag der wissenschaftlichen Aussprache: 27. Juni 2011
Berlin 2011
D 833
Zusammenfassung
Eine wichtige Aufgabe der diskreten Mathematik besteht in der Kategorisierung
von kombinatorischen Optimierungsproblemen nach ihrem Schwierigkeitsgrad. Die
grundlegendsten und bekanntesten Komplexit¨atsklassen sind zweifelsohne P und NP.
AufPundNPbautsichdiepolynomielleHierarchieauf,dieausvielenweiterenKom-
plexit¨atsklassen besteht, deren Probleme schwerer zu sein scheinen als die Probleme
p
in P und NP. Die Komplexit¨atsklasse Σ liegt in dieser Hierarchie eine Stufe u¨ber NP2
undenth¨altalldieProbleme, diedurcheinennichtdeterministischenAlgorithmusmit
Hilfe eines NP-Orakels gel¨ost werden k¨onnen. Im Gegensatz zu den Klassen P und
pNPerfreutsichdieKlasseΣ geringererBekanntheit,wasunteranderemdaranliegen2
mag, dass sie naturgem¨ass komplizierter ist, und man bisher nur wenige natu¨rliche
Probleme kennt, die bezu¨glich dieser Klasse vollst¨andig sind.
DerHauptbeitragdervorliegendenArbeitliegtinderEntwicklungeinerneuenMetho-
p p
de,dieeserlaubt,ganzeKlassenvonProblemen,dieinΣ liegen,alsΣ -vollst¨andigzu2 2
beweisen. Diese Technik benutzt bestimmte Eigenschaften bestehender Transforma-
tionen zwischen NP-vollst¨andigen Problemen, um eine polynomielle Transformation
p p
von einem Σ -vollst¨andigen Problem zu einer in Σ liegenden Variante eines anderen2 2
Problems zu erzeugen. Damit zeigt diese Arbeit nicht nur neue, durchaus natu¨rliche
p
und grundlegende, Σ -vollst¨andige Probleme auf, sondern steuert ganze Familien von2
pProblemen bei, die Σ -vollst¨andig sind.2
Zu dieser Art von Problemen geh¨oren Varianten von in 0-1 Variablen formulierbaren
Zul¨assigkeitsproblemen, bei denen man fragt, ob es fu¨r eine vorgegebene Teilmenge
der Variablen eine 0-1 Zuweisung gibt, so dass fu¨r die restlichen Variablen keine 0-1
Belegung mehr m¨oglich ist, die zu einer insgesamt zul¨assigen Lo¨sung fu¨hren wu¨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¨osung des Problems zu verkleinern, indem man fu¨r
einzelne Variablenbelegungen testet, ob sie u¨berhaupt Teil einer optimalen L¨osung
p
sein k¨onnen. Eine weitere Klasse von Σ -vollst¨andigen Problemen ergibt sich aus2
Fragen nach der Existenz von Gegenbeispielen fu¨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 Ha-
miltonischen Kreis haben. Zus¨atzliche Probleme und Problemklassen, die in dieser
p
ArbeitalsΣ -vollst¨andigbewiesenwerden,betreffenFragestellungenwiedenVersuch,2
eine beschr¨ankte Anzahl der Variablen so zu belegen, dass es genau eine zul¨assige Er-
weiterung dazu gibt, oder die Aufgabe herauszufinden, ob ein gegebenes ganzzahliges
Optimierungsproblem u¨berflu¨ssige Ungleichungen enth¨alt.Abstract
An important aspect of discrete optimization is to analyze the computational com-
plexity 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
pmost interesting class is arguably Σ , which is the central topic of this thesis. The2
p
complexity class Σ lies one level above the class NP and contains all decision prob-2
lems that can be solved efficiently by a nondeterministic algorithm that has access to
p
anNPoracle. IncontrasttothecomplexityclassesPandNP,theclassΣ hasnotyet2
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
pΣ -completeness for entire classes of problems. We show how and under which cir-2
cumstances a polynomial time transformation from one NP-complete problem Π to1
another NP-complete problem Π can be used to derive a polynomial time transfor-2
p
mation from an established Σ -complete problem corresponding to Π to a version of12
p p
Π in Σ , which is then, as a consequence, Σ -complete as well. As a result, we will2 2 2
p
provide many families of complete problems for Σ , most of which are quite natural,2
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
p
Σ -complete to decide whether there exists a counterexample to an NP-conjecture.2
An example of such a problem would be the question whether a graph with a certain
p
property is Hamiltonian or not. More problems that are shown to be Σ -complete2
include defining set problems which ask whether for a given instance of a decision
problemthereisapartialsolutionofacertainsizethatcanbecompletedtoafeasible
solutioninauniqueway,andtheproblemofdecidingwhetheragivenintegerprogram
has redundant constraints.Contents
Zusammenfassung 3
Abstract 4
1 Introduction 8
1.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 The Polynomial Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . 14
p
1.3 Brief History of Σ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
2 Adversarial Problems 24
2.1 A Generic Class of Adversarial Problems . . . . . . . . . . . . . . . . 26
2.2 Adversarial 3-Dimensional Matching . . . . . . . . . . . . . . . . . . 32
2.3 Adversarial Partition Problem . . . . . . . . . . . . . . . . . . . . . . 38
3 Multilevel Programming 44
3.1 Bilevel 0-1 Integer Programming . . . . . . . . . . . . . . . . . . . . . 46
3.2 Trilevel Linear Programming . . . . . . . . . . . . . . . . . . . . . . . 48
4 Preprocessing Problems 56
4.1 Preprocessing Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 A Generic Class of Preprocessing Problems . . . . . . . . . . . . . . . 61
4.3 Preprocessing Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . 66
4.4 Preprocessing 3-Dimensional Matching . . . . . . . . . . . . . . . . . 71
5CONTENTS 6
4.5 Preprocessing Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . 72
4.6 Beyond Value Preserving Transformations . . . . . . . . . . . . . . . 78
5 Counterexamples to NP-Conjectures 79
5.1 Hamiltonian Cycle Conjectures . . . . . . . . . . . . . . . . . . . . . 80
5.2 Counterexamples to NP-Conjectures . . . . . . . . . . . . . . . . . . 88
5.3 Counterexample to Vertex Cover Conjectures . . . . . . . . . . . . . 93
p
6 More Σ -Complete Problems 952
6.1 Cost Denying Set Problems . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.1 Cost Denying 3-Satisfiability . . . . . . . . . . . . . . . . . . . 95
6.1.2 Generic Cost Denying Set . . . . . . . . . . . . . . . . . . . . 97
6.2 Defining Set Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2.1 Minimum Defining Vertex Cover. . . . . . . . . . . . . . . . . 103
6.3 Constraint Redundancy Problems . . . . . . . . . . . . . . . . . . . . 105
Bibliography 109List of Figures
1-1 The polynomial hierarchy . . . . . . . . . . . . . . . . . . . . . . . . 18
2-1 Bijective function g between two problems in NP . . . . . . . . . . . 30
2-2 Transitivecombinationoftwovaluepreservingpolynomialtransforma-
tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2-3 Transformation from (3SAT) to (3DM) . . . . . . . . . . . . . . . . . 36
2-4 Application of Theorem 2.1.1 to (ADV-3DM) . . . . . . . . . . . . . 37
2-5 Transformation from (3DM) to (PRT) . . . . . . . . . . . . . . . . . 41
2-6 Link between the solutions of the (3DM) and the (PRT) instance . . 42
4-1 Transformation from (3SAT) to (VC) . . . . . . . . . . . . . . . . . . 70
4-2 Example solution for the (VC) instance of Figure 4-1 . . . . . . . . . 70
4-3 Application of Theorem 4.3.1 to (PP-VC) . . . . . . . . . . . . . . . 71
4-4 Cover-testing component used in the transformation from vertex
cover to hamiltonian cycle . . . . . . . . . . . . . . . . . . . . . 74