# The Helping Hierarchy

Patrizio Cintioli; Riccardo Silvestri

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 35, Issue: 4, page 367-377
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCintioli, Patrizio, and Silvestri, Riccardo. "The Helping Hierarchy." RAIRO - Theoretical Informatics and Applications 35.4 (2010): 367-377. <http://eudml.org/doc/222020>.

@article{Cintioli2010,

abstract = {
Schöning [14] introduced a notion of helping and suggested
the study of the class $\{\rm P\}_\{\rm help\}(\{\cal C\})$ of the languages that can be helped
by oracles in a given class $\{\cal C\}$. Later, Ko [12], in order to
study the connections between helping and "witness searching" ,
introduced the notion of self-helping for languages.
We extend this notion to classes of languages and show that there exists
a self-helping class that we call SH which contains all the
self-helping classes.
We introduce the Helping hierarchy whose
levels are obtained applying a constant number of times the operator
$\{\rm P\}_\{\rm help\}(\cdot)$ to the set of all the languages. We show that the Helping
hierarchy collapses to the k-th level if and only if SH is equal to the
k-th level. We give characterizations of all the levels and use these
to construct a relativized world in which the Helping
hierarchy is infinite.
},

author = {Cintioli, Patrizio, Silvestri, Riccardo},

journal = {RAIRO - Theoretical Informatics and Applications},

language = {eng},

month = {3},

number = {4},

pages = {367-377},

publisher = {EDP Sciences},

title = {The Helping Hierarchy},

url = {http://eudml.org/doc/222020},

volume = {35},

year = {2010},

}

TY - JOUR

AU - Cintioli, Patrizio

AU - Silvestri, Riccardo

TI - The Helping Hierarchy

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 4

SP - 367

EP - 377

AB -
Schöning [14] introduced a notion of helping and suggested
the study of the class ${\rm P}_{\rm help}({\cal C})$ of the languages that can be helped
by oracles in a given class ${\cal C}$. Later, Ko [12], in order to
study the connections between helping and "witness searching" ,
introduced the notion of self-helping for languages.
We extend this notion to classes of languages and show that there exists
a self-helping class that we call SH which contains all the
self-helping classes.
We introduce the Helping hierarchy whose
levels are obtained applying a constant number of times the operator
${\rm P}_{\rm help}(\cdot)$ to the set of all the languages. We show that the Helping
hierarchy collapses to the k-th level if and only if SH is equal to the
k-th level. We give characterizations of all the levels and use these
to construct a relativized world in which the Helping
hierarchy is infinite.

LA - eng

UR - http://eudml.org/doc/222020

ER -

## References

top- V. Arvind, A Note on the Self-Witnessing Property of Computational Problems, Proc. 2nd Annual International Conference on Computing and Combinatorics (COCOON'96). Springer-Verlag, Lecture Notes in Comput. Sci. 1090 (1996) 241-249.
- J.L. Balcázar, Self-reducibility, Proc. 4th Symposium on Theoretical Aspects of Computer Science. Springer-Verlag, Lecture Notes in Comput. Sci. 247 (1987) 136-147. Zbl0628.68048
- J.L. Balcázar, Self-reducibility structures and solutions of NP problems. Rev. Mat. Complut.2 (1989) 175-184. Zbl0687.68018
- D.P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity. Prentice-Hall (1994). Zbl0809.68067
- J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I, Vol. 1. Springer-Verlag (1988). Zbl0638.68040
- J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity II, Vol. 2. Springer-Verlag (1990). Zbl0746.68032
- J. Cai, L. Hemachandra and J. Viskoc, Promises Problems and Access to Unambiguous Computation, Proc. 17th Symposium on Mathematical Foundations of Computer Science. Springer-Verlag, Lecture Notes in Comput. Sci. 629 (1992) 162-171.
- P. Cintioli and R. Silvestri, Helping by Unambiguous Computation and Probabilistic Computation. Theory Comput. Syst.30 (1997) 165-180. Zbl0876.68065
- P. Cintioli and R. Silvestri, Revisiting a Result of Ko. Inform. Process. Lett.61 (1997) 189-194. Zbl1336.68087
- M. Fellows and N. Koblitz, Self-witnessing polynomial time complexity and prima factorization, in Proc. 6th Structure in Complexity Theory Conference (1992) 107-110. Zbl0756.11042
- L. Hemachandra, Fault-Tolerance and Complexity, in Proc. 20th International Colloquium on Automata, Languages, and Programming. Springer-Verlag, Lecture Notes in Comput. Sci. (1993).
- K. Ko, On Helping by Robust Oracle Machines. Theoret. Comput. Sci.52 (1987) 15-36. Zbl0635.68039
- M. Ogihara, On Helping by Parity-like Languages. Inform. Process. Lett.54 (1995) 41-43. Zbl1023.68616
- U. Schöning, Robust Algorithms: A Different Approach to oracles. Theoret. Comput. Sci.40 (1985) 57-66. Zbl0574.68041

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.