The helping hierarchy

Cintioli, Patrizio ; Silvestri, Riccardo

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

Résumé

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}}(·)$ 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.

Détail

Classification : 68Q15, 68Q05, 03D15