The helping hierarchy
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 4, pp. 367-377.

Schöning [14] introduced a notion of helping and suggested the study of the class ${\mathrm{P}}_{\mathrm{help}}\left(𝒞\right)$ of the languages that can be helped by oracles in a given class $𝒞$. 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 $\mathrm{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 ${\mathrm{P}}_{\mathrm{help}}\left(·\right)$ to the set of all the languages. We show that the Helping hierarchy collapses to the $k$-th level if and only if $\mathrm{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.

Classification : 68Q15,  68Q05,  03D15
@article{ITA_2001__35_4_367_0,
author = {Cintioli, Patrizio and Silvestri, Riccardo},
title = {The helping hierarchy},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {367--377},
publisher = {EDP-Sciences},
volume = {35},
number = {4},
year = {2001},
zbl = {1052.68050},
mrnumber = {1880805},
language = {en},
url = {http://www.numdam.org/item/ITA_2001__35_4_367_0/}
}
TY  - JOUR
AU  - Cintioli, Patrizio
AU  - Silvestri, Riccardo
TI  - The helping hierarchy
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
DA  - 2001///
SP  - 367
EP  - 377
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_4_367_0/
UR  - https://zbmath.org/?q=an%3A1052.68050
UR  - https://www.ams.org/mathscinet-getitem?mr=1880805
LA  - en
ID  - ITA_2001__35_4_367_0
ER  - 
Cintioli, Patrizio; Silvestri, Riccardo. The helping hierarchy. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 4, pp. 367-377. http://www.numdam.org/item/ITA_2001__35_4_367_0/

[1] 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.

[2] 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. | MR 900448 | Zbl 0628.68048

[3] J.L. Balcázar, Self-reducibility structures and solutions of NP problems. Rev. Mat. Complut. 2 (1989) 175-184. | MR 1031693 | Zbl 0687.68018

[4] D.P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity. Prentice-Hall (1994). | MR 1311246 | Zbl 0809.68067

[5] J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I, Vol. 1. Springer-Verlag (1988). | MR 1047862 | Zbl 0638.68040

[6] J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity II, Vol. 2. Springer-Verlag (1990). | MR 1056474 | Zbl 0746.68032

[7] J. Cai, L. Hemachandra and J. Viskoč, 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. | MR 1255134

[8] P. Cintioli and R. Silvestri, Helping by Unambiguous Computation and Probabilistic Computation. Theory Comput. Syst. 30 (1997) 165-180. | MR 1424935 | Zbl 0876.68065

[9] P. Cintioli and R. Silvestri, Revisiting a Result of Ko. Inform. Process. Lett. 61 (1997) 189-194. | MR 1438859

[10] M. Fellows and N. Koblitz, Self-witnessing polynomial time complexity and prima factorization, in Proc. 6th Structure in Complexity Theory Conference (1992) 107-110. | MR 1249968

[11] L. Hemachandra, Fault-Tolerance and Complexity, in Proc. 20th International Colloquium on Automata, Languages, and Programming. Springer-Verlag, Lecture Notes in Comput. Sci. (1993).

[12] K. Ko, On Helping by Robust Oracle Machines. Theoret. Comput. Sci. 52 (1987) 15-36. | MR 918111 | Zbl 0635.68039

[13] M. Ogihara, On Helping by Parity-like Languages. Inform. Process. Lett. 54 (1995) 41-43. | MR 1332420 | Zbl 1023.68616

[14] U. Schöning, Robust Algorithms: A Different Approach to oracles. Theoret. Comput. Sci. 40 (1985) 57-66. | MR 828516 | Zbl 0574.68041