The Helping Hierarchy

¹ 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 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 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.