The helping hierarchy

Patrizio Cintioli; Riccardo Silvestri

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

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

Abstract

top
Schöning [14] introduced a notion of helping and suggested the study of the class P help ( 𝒞 ) 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 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 P help ( · ) 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.

How to cite

top

Cintioli, Patrizio, and Silvestri, Riccardo. "The helping hierarchy." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.4 (2001): 367-377. <http://eudml.org/doc/92671>.

@article{Cintioli2001,
abstract = {Schöning [14] introduced a notion of helping and suggested the study of the class $\{\rm P\}_\{\rm help\}(\{\mathcal \{C\}\})$ of the languages that can be helped by oracles in a given class $\{\mathcal \{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 $\{\rm 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 $\{\rm 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 - Informatique Théorique et Applications},
language = {eng},
number = {4},
pages = {367-377},
publisher = {EDP-Sciences},
title = {The helping hierarchy},
url = {http://eudml.org/doc/92671},
volume = {35},
year = {2001},
}

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
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}({\mathcal {C}})$ of the languages that can be helped by oracles in a given class ${\mathcal {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 ${\rm 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 ${\rm 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/92671
ER -

References

top
  1. [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. [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. Zbl0628.68048MR900448
  3. [3] J.L. Balcázar, Self-reducibility structures and solutions of NP problems. Rev. Mat. Complut. 2 (1989) 175-184. Zbl0687.68018MR1031693
  4. [4] D.P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity. Prentice-Hall (1994). Zbl0809.68067MR1311246
  5. [5] J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I, Vol. 1. Springer-Verlag (1988). Zbl0638.68040MR1047862
  6. [6] J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity II, Vol. 2. Springer-Verlag (1990). Zbl0746.68032MR1056474
  7. [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. MR1255134
  8. [8] P. Cintioli and R. Silvestri, Helping by Unambiguous Computation and Probabilistic Computation. Theory Comput. Syst. 30 (1997) 165-180. Zbl0876.68065MR1424935
  9. [9] P. Cintioli and R. Silvestri, Revisiting a Result of Ko. Inform. Process. Lett. 61 (1997) 189-194. Zbl1336.68087MR1438859
  10. [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. MR1249968
  11. [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. [12] K. Ko, On Helping by Robust Oracle Machines. Theoret. Comput. Sci. 52 (1987) 15-36. Zbl0635.68039MR918111
  13. [13] M. Ogihara, On Helping by Parity-like Languages. Inform. Process. Lett. 54 (1995) 41-43. Zbl1023.68616MR1332420
  14. [14] U. Schöning, Robust Algorithms: A Different Approach to oracles. Theoret. Comput. Sci. 40 (1985) 57-66. Zbl0574.68041MR828516

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.