RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

DOI: 10.1051/ita:2001101

Theoret. Informatics Appl. 35, 367-377 (2001)

The Helping Hierarchy

Patrizio Cintioli¹ and Riccardo Silvestri²

¹ Dipartimento di Matematica e Fisica, Università di Camerino, Via Madonna delle Carceri, 62032 Camerino (MC), Italy; (cintioli@campus.unicam.it)
² Dipartimento di Scienze dell'Informazione, Università di Roma "La Sapienza" , Via Salaria 113, 00198 Roma, Italy; (silvestri@dsi.uniroma1.it)

(Received June, 2000. Accepted November, 2001)

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 ${\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.

What is OpenURL?