On some promise classes in structural complexity theory [Elektronische Ressource] / von Jörg Rothe

Sujets

• Informatik

Informations

• Publié par: friedrich-schiller-universitat_jena
• Publié le: 01 janvier 1995
• Nombre de lectures: 40
• Langue: English

Extrait

On Some Promise Classes
in Structural Complexity Theory
Dissertation
zur Erlangung des akademischen Grades
doctor rerum naturalium (Dr. rer. nat.)
vorgelegt dem Rat der
Fakultat¨ fur¨ Mathematik und Informatik
der Friedrich-Schiller-Universitat¨ Jena
von Diplom-Mathematiker
Jor¨ g Rothe
geb. am 1. November 1966 in ErfurtGutachter: Prof. Dr. Gerd Wechsung
Prof. Lane A. Hemaspaandra
Prof. Dr. Uwe Schoning¨
Tag des Rigorosums: 5. Oktober 1995
¨Tag der offentlichen Verteidigung: 12. 1995To my parentsivAcknowledgments
Professor Gerd Wechsung, my advisor, has been the most influential and decisive person
regarding my scientific career. He not only nurtured my pleasure in mathematics when I was
an undergraduate student but also introduced me to the joy and challenge of doing research.
I very much appreciate his inspiring and enthusiastic way of creating and formalizing ideas
and his graceful style of holding lectures as well as his humane warmth, grace, and optimism.
I am particularly grateful to him for bringing about my collaboration with Professor Lane
Hemaspaandra and, in general, for his constant encouragement and support.
I am very grateful to Professor Lane Hemaspaandra for his kind guidance, insightful
advice, and seminal collaboration during my one year stay at the University of Rochester
and ever since. His scientific enthusiasm and his flood of wonderful ideas, comments, and
suggestions that contributed to the research described in this work have been invaluable for
this thesis and, in fact, made it possible at all. Particularly, I am much indebted to him for
having me take part in, and contribute to, his research projects, which eventually led to the
first three sections of Chapter 3 and to Chapter 5 of this thesis. From him I learned that
striking out in new directions from the solid foundation of being well versed in one’s field,
combined with the American virtue, speed in getting done whatever one aims at,isthemost
crucial prerequisite for successful work. In addition, I thank him for his financial support
that allowed me to present the results contained in the fourth section of Chapter 3 at the
Sixth International Conference on Computing and Information in Peterborough, Ontario,
in May, 1994.
I thank Professor Lane Hemaspaandra and Professor Uwe Schoning¨ for kindly agreeing
to serve—in addition to my advisor, Professor Wechsung—as referees for this thesis.
I further thank all my coauthors, including Lane Hemaspaandra, Osamu Watanabe,
Zhigen Jiang, Rajesh Rao, Gerd Wechsung, and Jor¨ g Vogel, in Rochester, Tokyo, and
vvi Acknowledgments
Jena for our wonderful collaboration in many projects and for their generous permission
to present the results of our joint papers in this thesis. In particular, I’d like to mention
that Osamu Watanabe’s idea of looking at Buhrman, E. Hemaspaandra, and Longpre’´ s tally
encoding of sparse sets ignited the research described in Chapter 4 of this thesis, and I again
have to thank Lane Hemaspaandra for proposing the investigation of the upward separation
technique regarding promise classes. I also thank Arfst Nickelsen and Johannes Kobler¨ for
their permission to state and cite still unpublished results of theirs in this work.
Furthermore, I thank all my current and former colleagues, Gerhard Lischke, Jor¨ g
Vogel (who was supervising my diploma thesis in 1991), Dieter Kratsch, Haiko Mulle¨ r,
Arfst Nickelsen, Harald Hempel, Johannes Waldmann, Peter Sauer, Dietmar Schuchardt,
Zhigen Jiang, Rajesh Rao, Polly Pook, Marc Light, Mitsunori Ogihara, Yenjo Han, Ioan
Macarie, and Marius Zimand, from Jena and Rochester. In particular, I’d like to express
my gratitude to Johannes Waldmann, Dieter Kratsch, and Haiko Muller¨ for spending much
Aof their time with explaining to me the subtleties of the local Jena LT X installation.E
The German Academic Exchange Service (DAAD) generously supported with a fel-
lowship my research at the University of Rochester, and the American National Science
Foundation (NSF) also supported in part my research under grants NSF-CCR-8957604
and NSF-CCR-9322513.
For a lifetime of understanding, love, and advice, I’m grateful to my family, especially
to my parents, to all my friends in Jena and Rochester, and, chiefly, to my wife, Irene, for
her great patience and love during the hectic period in which this thesis was written and for
the wonderful time we together enjoyed in Rochester and Jena.Contents
List of Figures ix
1 Introduction 1
2 Notations 7
2.1 Strings,Sets,Functions,andBooleanOperations.............. 7
2.2 Machines and Reducibilities . . ............... 8
2.3 ComplexityClasesandOperators.................. 10
2.4 PromiseClases........................ 13
3 UP: Boolean Hierarchies and Sparse Turing-Complete Sets 17
3.1 Introduction . . . . .............................. 17
3.2 BooleanHierarchiesoverClasesClosedUnderIntersection.... 20
3.3 SparseTuring-completeandTuring-hardSetsforUP............ 32
3.4 PromiseSPPisatLeastasHardasthePolynomialHierarchy.... 41
4 Upward Separation for FewP and Related Classes 47
4.1 Introduction . . . . .............................. 47
4.2 Preliminaries . . ........... 49
4.3 UpwardSeparationResults.......................... 50
4.4 ConclusionsandOpenProblems....... 54
5 Multi-Selectivity and Complexity-Lowering Joins 57
5.1 Introduction . . . . .............................. 57
5.2 ABasicHierarchyofGeneralizedSelectivityClasses.... 59
5.2.1 Structure, Properties, and Relationships with P-mc Classes ..... 59
viiviii Contents
5.2.2 Circuit, Lowness, and Collapse Results . . . ............ 70
5.3 ExtendedLownesandtheJoinOperator........... 73
5.4 An Extended Selectivity Hierarchy Capturing Boolean Closures of P-Sel . . 78
A Some Proofs from Chapter 5 93
Index 97
Bibliography 101List of Figures
UP3.1 DPOM guardedly accessing an oracle from
UP to accept a set in UP .36
3.2 A self-reducing machine for the left set of a UP set. . ............ 39
3.3 A Turing reduction from a UP set to its left set via prefix search. . . . . 39
5.1 An S 1 -selector for ......................... 62
5.2 InclusionrelationshipsamongS,fair-S,andP-mcclases....... 67
5.3 Relations between all nontrivial classes GC with 1 3. . 89
ix


k
g
c;
)
A
+
(
(
b;
b;
d
c;
B
d
M
)
A
kx List of Figures