Schöning [14] introduced a notion of helping and suggested the study of the class 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 which contains all the self-helping classes. We introduce the Helping hierarchy whose levels are obtained applying a constant number of times the operator to the set of all the languages. We show that the Helping hierarchy collapses to the -th level if and only if is equal to the -th level. We give characterizations of all the levels and use these to construct a relativized world in which the Helping hierarchy is infinite.
@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}, mrnumber = {1880805}, zbl = {1052.68050}, language = {en}, url = {http://archive.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 SP - 367 EP - 377 VL - 35 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_2001__35_4_367_0/ LA - en ID - ITA_2001__35_4_367_0 ER -
%0 Journal Article %A Cintioli, Patrizio %A Silvestri, Riccardo %T The helping hierarchy %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2001 %P 367-377 %V 35 %N 4 %I EDP-Sciences %U http://archive.numdam.org/item/ITA_2001__35_4_367_0/ %G en %F ITA_2001__35_4_367_0
Cintioli, Patrizio; Silvestri, Riccardo. The helping hierarchy. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 35 (2001) no. 4, pp. 367-377. http://archive.numdam.org/item/ITA_2001__35_4_367_0/
[1] 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] Self-reducibility, Proc. 4th Symposium on Theoretical Aspects of Computer Science. Springer-Verlag, Lecture Notes in Comput. Sci. 247 (1987) 136-147. | MR | Zbl
,[3] Self-reducibility structures and solutions of NP problems. Rev. Mat. Complut. 2 (1989) 175-184. | MR | Zbl
,[4] Introduction to the Theory of Complexity. Prentice-Hall (1994). | MR | Zbl
and ,[5] Structural Complexity I, Vol. 1. Springer-Verlag (1988). | MR | Zbl
, and ,[6] Structural Complexity II, Vol. 2. Springer-Verlag (1990). | MR | Zbl
, and ,[7] 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
, and ,[8] Helping by Unambiguous Computation and Probabilistic Computation. Theory Comput. Syst. 30 (1997) 165-180. | MR | Zbl
and ,[9] Revisiting a Result of Ko. Inform. Process. Lett. 61 (1997) 189-194. | MR
and ,[10] Self-witnessing polynomial time complexity and prima factorization, in Proc. 6th Structure in Complexity Theory Conference (1992) 107-110. | MR
and ,[11] Fault-Tolerance and Complexity, in Proc. 20th International Colloquium on Automata, Languages, and Programming. Springer-Verlag, Lecture Notes in Comput. Sci. (1993).
,[12] On Helping by Robust Oracle Machines. Theoret. Comput. Sci. 52 (1987) 15-36. | MR | Zbl
,[13] On Helping by Parity-like Languages. Inform. Process. Lett. 54 (1995) 41-43. | MR | Zbl
,[14] Robust Algorithms: A Different Approach to oracles. Theoret. Comput. Sci. 40 (1985) 57-66. | MR | Zbl
,