Structural properties of NP-hard sets and uniform characterisations of complexity classes [Elektronische Ressource] / vorgelegt von Stephen Travers

Sujets

• Mathematics

Informations

• Publié par: julius-maximilians-universitat_wurzburg
• Publié le: 01 janvier 2008
• Nombre de lectures: 27
• Langue: Deutsch

Extrait

Structural Properties of NP-Hard Sets and
Uniform Characterisations of Complexity Classes
Dissertation zur Erlangung des
naturwissenschaftlichen Doktorgrades
der Julius-Maximilians-Universit¨ at Wurz¨ burg
vorgelegt von
Stephen Travers
aus Frankfurt am Main
W¨ urzburg, 2007
Julius-Maximilians-Universit¨ at Wurz¨ burg
Fakultat¨ fur¨ Mathematik und InformatikEingereicht am: 6. Dezember 2007 bei der
Fakultat¨ fur¨ Mathematik und Informatik,
Julius-Maximilians Universit¨ at Wurz¨ burg
1. Gutachter: Prof. Dr. Klaus W. Wagner
2. Gutachter: Prof. Dr. Edith Hemaspaandra
Tag der mundl¨ ichen Pru¨fung: 11. April 2008Meinen Eltern.Ich bedanke mich bei allen, die mich wa¨hrend der Entstehung dieser Arbeit unterstut¨ zt
haben. Besonderer Dank gilt meinem Doktorvater Klaus W. Wagner fur¨ die sehr gute
Betreuung, seine hilfreichen Anregungen sowie die hervorragende Arbeitsatmosph¨ are an
seinem Lehrstuhl. Besonders hervorheben m¨ochte ich auch Christian Glaßer, der mich
gleich zu Beginn meiner Zeit am Lehrstuhl in die aktuelle Forschung eingebunden hat.
Durch die Zusammenarbeit mit ihm und durch seinen schier unerscho¨pflichen Erfahrungs-
schatz habe ich sehr viel gelernt, und seine sta¨ndige Motivation und Unterstut¨ zung haben
viel zum Gelingen dieser Arbeit beigetragen.
Meinen aktuellen und ehemaligen Kollegen Elmar B¨ ohler, Daniel Meister und Christian
Reitwießner danke ich dafu¨r, dass sie dazu beigetragen haben, die Zeit am Lehrstuhl zu
einer angenehmen und interessanten zu machen.
Schließlich mo¨chte ich meinen Eltern und auch meinem Bruder danken, die mich stets in
meinem Tun unterstu¨tzt haben und auf deren Vertrauen ich mich immer verlassen konnte.
Meiner Frau Nora danke ich fur¨ alles. Im Zusammenhang mit der Entstehung dieser Arbeit
danke ich ihr insbesondere fur¨ die Geduld und ihre permanente Unterstut¨ zung.
Der Konrad-Adenauer-Stiftung danke ich fur¨ die Gewa¨hrung eines Promotionsstipendiums.
W¨ urzburg, im Dezember 2007 Stephen TraversContents
Introduction ...................................... 9
1 Preliminary Notions, Basic Notations, and Definitions ........ 19
1.1 Numbers,Words,Sets,andOperators.................19
1.2 PrinciplesofComputationalComplexityTheory ...........21
1.2.1 TuringMachines.........................21
1.2.2 Complexity-andFunctionClases...............2
1.2.3 Relativisation...........................26
1.2.4 Reducibilities...................27
1.2.5 SomeStructuralProperties...................29
1.3 RecursionTheory.............................30
I Structural Properties of NP-Hard Sets 33
2 Unions of Disjoint, Equivalent NP-Sets .................. 35
2.1 ADigresiontoRecursionTheory ...............38
2.2 NecessaryandSufficientConditions ......................40
2.2.1 P-SeparableSetsandPaddableSets..................41
2.3 Evidence for the Complexity of Unions of Disjoint NP-Complete Sets . . . . 44
2.3.1 TheHigh-Hierarchy...........................4
2.3.2 A Non-Uniform Reducibility . . . . . . . .......46
2.4 Upper and Lower Bounds . . . . ........................48
2.4.1 M-IdempotentSets................49
2.4.2 HarderUnions..............................57
2.5 SummaryandOutlook..................59
3 NP-Hard Sets and Faulty Data ........................ 61
3.1 WeakDeterministicSelf-Corection...............62
3.2 PartlyCorruptNP-HardSets..........................64
3.2.1 Many-OneReductions..........................64
3.2.2 DisjunctiveTruth-TableReductions..........683.2.3 ConjunctiveTruth-TableReductions..................7
3.2.4 Non-RobustnesAgainstSparseSetsofFalsePositives........80
3.3 SummaryandOutlook..............................83
4 Partitioning NP-Sets ............................... 85
4.1 SeparationofMitoticityNotions ....................86
4.2 Non-T-MitoticSetsinNP........................89
4.3 SummaryandOutlook......................92
II Uniform Computation Models 95
5 The Leaf-Language Approach ......................... 97
5.1 AnIntroductiontoLeafLanguages...............98
5.1.1 A Connection between Complexity Theory and Formal Languages . 99
5.1.2 OracleSeparations............................101
6 Unbalanced Leaf-Language Classes .....................103
6.1 PerfectCorespondences.....................104
6.2 Polynomial-Time Tree Reducibility . . . . . ..................106
6.3 The ptt-Reducibility and the Dot-Depth Hierarchy . . . . . .....108
6.4 SummaryandOutlook..............................17
7 ε-Leaf-Language Classes ............................119
7.1 The ε-Leaf-LanguageModel...............19
7.1.1 Polylogarithmic-Time ε-Reducibility ..................121
7.1.2 A Connection to the Straubing-Th´erienHierarchy ......12
7.2 GapTheoremsandPerfectCorespondences..................124
P P7.3 Gap Theorems for NP, Δ ,andΣ ..............125
2 2
7.4 A Characterisation of 1NP ...........................129
7.5 AnOverview.......................139
Bibliography ......................................143
Index ...........................................1539
Introduction
Computational complexity theory is a branch of theoretical computer science. The cen-
tral question posed in this scientific discipline is the question of how difficult concrete
algorithmic problems are.
What is a concrete algorithmic problem? Generally, there are few limitations, as long as
the problem’s definition is mathematically sound and unambiguous. The following are
classical examples.
1. Given a map, what is the optimal route from one city A to another city B?
2. Given a natural number, what is its greatest prime factor?
3. Given a formula in propositional calculus with n variables, is there an assignment of
truth-values to the variables such that the whole expression evaluates to true?
4. Given a map, a delivery truck stacked with parcels, and a list of n locations on the
map where parcels are to be delivered. What is the minimum distance of this round
trip?
5. Given a list of n natural numbers, and a natural number m. Is there a subset of
these numbers whose sum is precisely m?
When we talk about the difficulty of algorithmic problems, the term difficult does not refer
to the difficulty of developing an algorithm to solve the problem. Instead, it refers to the
amount of resources needed to algorithmically compute the solution for a given problem
instance.
Problems3and5aredecision problems. Given a problem instance x, the answer is either
“yes” or “no”. On the other hand, algorithmic problems are often optimisation problems,
like the problems 1 and 4 in the list above. Given a problem instance x,theanswertox
is a number y. The same holds true for problem 2. These problems are function problems.
The major part of computational complexity theory (or complexity theory, for short) deals
with decision problems, and so does this thesis. Interestingly, this is not a real restriction,
because function problems can in fact be simulated by decision problems.10
Let us assume we have an algorithm A which solves the following decision problem with
a certain amount of resources:
“Given natural numbers n and k,doesn have a prime factor greater than k?”
By doing a binary search on k and running the algorithm A multiple times with different
k’s, we can solve problem 2 without much more effort than A requires.
From a mathematical point of view, a decision problem is a set, and solving the yes-no
question for a given instance x is nothing more than deciding whether x belongs to the
set. For example, problem 3 can be represented by the set


{H H is a formula in propositional calculus and H is satisfiable}.
It remains to clarify how the resources consumed by algorithms are measured. Typically,
the scarce resources are time and space, and the complexity is measured with respect to
the size of the problem instance. Hence, the central question in complexity theory can be
restated as follows:
“As the size of the problem instance x for a set A increases, how do the running time
or memory requirements to solve the problem whether x belongs to A change?”
Complexity classes are families of problems that have a similar asymptotic behaviour. One
of the most prominent examples is the complexity class P, which comprises all decision
problems that can be solved by deterministic Turing machines in polynomial time. For
instance, Dijkstra’s algorithm [Dij59] solves the shortest path problem in polynomial time,
so the decision version of problem 1 is in P. For the other problems in our list, no
polynomial algorithms are known. However, it does not follow that the problems are not
in P, because it could be the case that better algorithms do exist and we just do not know
of them yet. It is easy to see that all problems in our list (or their decision version) are in
EXP, the class of decision problems solvable in deterministic exponential time.
An algorithm which decides a set A implies an upper bound for the complexity of A.
Complexity classes usually consist of problems which share the same upper bound. Prov-
ing lower bounds is often much more difficult than proving upper bounds. While one
algorithm suffices to prove an upper bound, a lower bound is a statement that no algo-
rithm whatsoever can