No CrossRef data available.
Article contents
The Helping Hierarchy
Published online by Cambridge University Press: 15 April 2002
Abstract
Schöning [14] introduced a notion of helping and suggestedthe study of the class ${\rm P}_{\rm help}({\cal C})$ 
of the languages that can be helpedby oracles in a given class ${\cal C}$ 
. Later, Ko [12], in order tostudy 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 existsa self-helping class that we call SH which contains all theself-helping classes.We introduce the Helping hierarchy whoselevels 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 Helpinghierarchy collapses to the k-th level if and only if SH is equal to thek-th level. We give characterizations of all the levels and use theseto construct a relativized world in which the Helpinghierarchy is infinite.
Information
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2001
References
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.
Balcázar, J.L., Self-reducibility structures and solutions of NP problems.
Rev. Mat. Complut.
2 (1989) 175-184.
CrossRef
D.P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity. Prentice-Hall (1994).
J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I, Vol. 1. Springer-Verlag (1988).
J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity II, Vol. 2. Springer-Verlag (1990).
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.
Cintioli, P. and Silvestri, R., Helping by Unambiguous Computation and Probabilistic Computation.
Theory Comput. Syst.
30 (1997) 165-180.
CrossRef
Cintioli, P. and Silvestri, R., Revisiting a Result of Ko.
Inform. Process. Lett.
61 (1997) 189-194.
CrossRef
M. Fellows and N. Koblitz, Self-witnessing polynomial time complexity and prima factorization, in Proc. 6th Structure in Complexity Theory Conference (1992) 107-110.
L. Hemachandra, Fault-Tolerance and Complexity, in Proc. 20th International Colloquium on Automata, Languages, and Programming. Springer-Verlag, Lecture Notes in Comput. Sci. (1993).
On Helping, K. Ko by Robust Oracle Machines.
Theoret. Comput. Sci.
52 (1987) 15-36.
Schöning, U., Robust Algorithms: A Different Approach to oracles.
Theoret. Comput. Sci.
40 (1985) 57-66.
CrossRef