Weak completeness notions for exponential time [Elektronische Ressource] / vorgelegt von Timur Bakibayev

English
193 Pages
Read an excerpt
Gain access to the library to view online
Learn more

Description

INAUGURAL - DISSERTATIONzurErlangung der Doktorwurde¨derNaturwissenschaftlich-Mathematischen Gesamtfakultat¨derRuprecht - Karls - Universitat¨Heidelbergvorgelegt vonTimur Bakibayevaus KaragandinskayaTag der mundlichen¨ Prufung:¨ 10.03.2010Weak Completeness Notions ForExponential TimeGutachter: Prof. Dr. Klaus Ambos-SpiesProf. Dr. Serikzhan BadaevAbstractThe standard way for proving a problem to be intractable is to show that theproblem is hard or complete for one of the standard complexity classes containingintractable problems. Lutz (1995) proposed a generalization of this approach byintroducing more general weak hardness notions which still imply intractability.While a set A is hard for a class C if all problems in C can be reduced to A (bya polynomial-time bounded many-one reduction) and complete if it is hard and amember of C, Lutz proposed to call a set A weakly hard if a nonnegligible part ofC can be reduced to A and to call A weakly complete if in addition A2 C. Forlin polythe exponential-time classes E= DTIME(2 ) and EXP= DTIME(2 ), Lutzformalized these ideas by introducing resource bounded (Lebesgue) measures onthese classes and by saying that a subclass of E is negligible if it has measure 0 inE (and similarly for EXP).

Subjects

Informations

Published by
Published 01 January 2010
Reads 18
Language English
Report a problem

INAUGURAL - DISSERTATION
zur
Erlangung der Doktorwurde¨
der
Naturwissenschaftlich-Mathematischen Gesamtfakultat¨
der
Ruprecht - Karls - Universitat¨
Heidelberg
vorgelegt von
Timur Bakibayev
aus Karagandinskaya
Tag der mundlichen¨ Prufung:¨ 10.03.2010Weak Completeness Notions For
Exponential Time
Gutachter: Prof. Dr. Klaus Ambos-Spies
Prof. Dr. Serikzhan BadaevAbstract
The standard way for proving a problem to be intractable is to show that the
problem is hard or complete for one of the standard complexity classes containing
intractable problems. Lutz (1995) proposed a generalization of this approach by
introducing more general weak hardness notions which still imply intractability.
While a set A is hard for a class C if all problems in C can be reduced to A (by
a polynomial-time bounded many-one reduction) and complete if it is hard and a
member of C, Lutz proposed to call a set A weakly hard if a nonnegligible part of
C can be reduced to A and to call A weakly complete if in addition A2 C. For
lin polythe exponential-time classes E= DTIME(2 ) and EXP= DTIME(2 ), Lutz
formalized these ideas by introducing resource bounded (Lebesgue) measures on
these classes and by saying that a subclass of E is negligible if it has measure 0 in
E (and similarly for EXP). A variant of these concepts, based on resource bounded
Baire category in place of measure, was introduced by Ambos-Spies (1996) where
now a class is declared to be negligible if it is meager in the corresponding resource
bounded sense.
In our thesis we introduce and investigate new, more general, weak hardness
notions for E and EXP and compare them with the above concepts from the litera-
ture.
The two main new notions we introduce are nontriviality, which may be viewed
as the most general weak hardness notion, and strong nontriviality. In case of E,
kna set A is E-nontrivial if, for any k 1, A has a predecessor in E which is 2
complex, i.e., which can only be computed by Turing machines with run times
knexceeding 2 on infinitely many inputs; and A is strongly E-nontrivial if there are
knpredecessors which are almost everywhere 2 complex.
Besides giving examples and structural properties of the E-(non)trivial and
strongly E-(non)trivial sets, we separate all weak hardness concepts for E, compare
the corresponding concepts for E and EXP, answer the question whether (strongly)
E-nontrivial sets are typical among the sets in E (or among the computable sets, or
among all sets), investigate the degrees of the (strongly) E-nontrivial sets, and an-
alyze the strength of these concepts if we replace the underlying p-m-reducibility
by some weaker polynomial-time reducibilities.Zusammenfassung
Will man zeigen, dass ein Problem zwar algorithmisch losbar¨ , aber nur schwer
(d.h. nicht in Polynomialzeit) losbar¨ ist, so macht man dies meist dadurch, dass
man das Problem als hart oder vollstandig¨ fur¨ eine Komplexitatsklasse¨ nachweist,
die schwer losbare¨ Probleme enthalt.¨ Lutz (1995) schlug eine Verallgemeinerung
dieses Ansatzes vor, die auf schwachen Harte-¨ bzw. Vollstandigk¨ eitsbegriffen ba-
siert. Wahrend¨ eine Menge A hart (oder schwer) fur¨ eine Komplexitatsklasse¨
C ist, wenn alle Probleme aus C auf A reduziert werden konnen¨ (mittels einer
polynomialzeit-bechrankten¨ many-one-Reduktion) und A vollstandig¨ fur¨ C ist,
wenn zusatzlich¨ A selbst in C liegt, nennt Lutz eine Menge A schwach hart, falls
ein nicht zu vernachlassig¨ ender Teil der Probleme aus C auf A reduzierbar ist,
und schwach vollstandig,¨ wenn wiederum zusatzlich¨ A2 C gilt. Im Falle der
lin polyExponentialzeit-Klassen E= DTIME(2 ) und EXP= DTIME(2 ) formalisierte
Lutz diese Ideen, indem er geeignete ressourcenbeschrankte¨ Varianten des Lebes-
gue-Maßes auf diesen Klassen einfuhrte¨ und Teilklassen von E vernachlassigbar¨
nennt, falls diese Maß 0 in E haben (und entsprechend fur¨ EXP). Eine Variante
dieser Konzepte, in der das Lebesgue-Maß durch Baire-Kategorie ersetzt ist, wurde
von Ambos-Spies (1996) vorgeschlagen. Hier sind die vernachlassigbaren¨ Teilk-
lassen diejenigen, die - im entsprechenden ressourcenbeschrankten¨ Sinne - mager
sind.
In unserer Dissertation fuhren¨ wir neue, allgemeinere schwache Hartebe¨ griffe
fur¨ E und EXP ein und vergleichen diese mit den oben genannten Konzepten aus
der Literatur.
Die zwei wichtigsten der von uns neu eingefuhrten¨ Konzepte sind die Nichttriv-
ialitat,¨ die als das allgemeinste schwache Hartek¨ onzept angesehen werden kann,
und die starke Nichttrivialitat.¨ Im Falle der Klasse E ist eine Menge A E-nichttrivial,
knfalls es fur¨ jedes k 1 eine Menge aus E gibt, die auf A reduzierbar ist und 2 -
komplex ist, d.h. nur von Turingmaschinen erkannt werden kann, deren Laufzeit
knauf unendlich vielen Eingaben die Schranke 2 uberschreitet;¨ und A ist stark E-
knnichttrivial, falls diese einen fast uberall¨ 2 -komplexen Vorganger¨ in E besitzt.
¨In unserer Arbeit geben wir Beispiele fur E-(nicht)triviale und stark E-(nicht)tri-
viale Mengen an, untersuchen deren Eigenschaften, trennen alle schwachen Voll-
standigk¨ eitsbegriffe fur¨ E, vergleichen die entsprechenden Begriffe fur¨ E und EXP,
beantworten die Frage, ob (stark) E-nichttriviale Mengen typisch sind (im Bezug
auf E, im Bezug auf die entscheidbaren Mengen und im Bezug auf alle Mengen),
untersuchen die (p-m-)Grade der (stark) E-(nicht)trivialen Mengen, und analysieren
die Stark¨ e der Varianten der schwachen Hartebe¨ griffe, bei denen die zugrundege-
legte p-m-Reduzierbarkeit durch allgemeinere Polynomialzeit-Reduzierbarkeiten
ersetzt ist.Contents
1 Introduction 1
2 The Exponential Time Classes 9
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Time Complexity Classes . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Polynomial Time Reducibilities . . . . . . . . . . . . . . . . . . 16
2.4 The Exponential Time Classes E and EXP . . . . . . . . . . . . . 20
2.5 Almost-Everywhere Complexity and Bi-Immunity . . . . . . . . 23
3 Weak Completeness Notions in the Literature 27
3.1 Computable and Time-Bounded Measure . . . . . . . . . . . . . 29
3.2 Lutz’s Measure Completeness . . . . . . . . . . . . . . . . . . . 41
3.3 Computable and T Baire Category . . . . . . . . . . 44
3.4 Ambos-Spies’ Category Completeness . . . . . . . . . . . . . . . 51
4 Nontriviality for E and EXP 55
4.1 E-Nontriviality: Definitions and Basic Facts . . . . . . . . . . . . 58
4.2 E-Trivial Sets in E . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3 E-Nontrivial Sets in E . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4 EXP-Nontriviality . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5 Intermediate Weak Completeness Notions 79
5.1 Strong Nontriviality . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Compression . . . . . . . . . . . . . . . . . . . . . 88
5.3 The Hierarchy of Weak Completeness Notions . . . . . . . . . . . 92
6 Comparing Weak Completeness for E and EXP 95
6.1 An E-Trivial EXP-Measure Complete Set . . . . . . . . . . . . . 97
6.2 An EXP-Trivial E-Nontrivial Set . . . . . . . . . . . . . . . . . . 105
6.3 Main Theorem on Comparing Weak Completeness for E and EXP 106
7 Nontrivial Sets Outside of E and EXP 109
7.1 Are Typical Sets E-Nontrivial? . . . . . . . . . . . . . . . . . . . 111
7.2 Noncomputable E-Trivial and E-Nontrivial Sets . . . . . . . . . . 112
7.3 Computable Strongly E-Nontrivial Sets . . . . . . . . . . . . . . 113
7.4 Some Examples of Computable E-Trivial Sets . . . . . . . . . . . 116
7.5 Computable E-Trivial Sets Are Not Rare . . . . . . . . . . . . . . 117
7.6 E-Nontrivial Sets Are Not Rare . . . . . . . . . . . . 122
7.7 Summary of Results . . . . . . . . . . . . . . . . . . . . . . . . . 124II CONTENTS
8 Nontriviality and Degrees 127
8.1 Trivial and Nontrivial E-Degrees . . . . . . . . . . . . . . . . . . 130
8.2 Weakly Trivial and Strongly Nontrivial E-Degrees . . . . . . . . . 137
9 Nontriviality with Respect to Other Reducibilities 147
9.1 r-E-Nontriviality and Strong r-E-Nontriviality . . . . . . . . . . . 150
9.2 Nontriviality vs. Strong Nontriviality and Strong Nontriviality vs.
Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9.3 Nontriviality Under 1-Query Reducibilities . . . . . . . . . . . . 153
9.4 Strong Nontriviality Under 1-Query Reducibilities . . . . . . . . . 156
9.5 Nontriviality and Strong Nontriviality Under Multi-Query Reduci-
bilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
9.6 Summary for E . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
9.7 Nontriviality for EXP with Respect to Other Reducibilities . . . . 172
10 Conclusion 177