Schoning introduced a notion of helping and suggested the study of the class $P_{hel}(C) of the languages that can be helped by oracles in a given class C. Later, Ko, in order to study the connections between helping and "witnessing 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 classes. We introduce the helping hierarchy whose levels are obtained applying a constant number of times the operator P_{help}() to the set all the languages. We show that the helping hierarchy collapses to the kth level if and only if SH is equal to the kth level. We give characterizations of all the levels and use these to construct a relativizeed world in which the Helping hierarchy is infinite.
The Helping Hierarchy.
CINTIOLI, Patrizio;
2001-01-01
Abstract
Schoning introduced a notion of helping and suggested the study of the class $P_{hel}(C) of the languages that can be helped by oracles in a given class C. Later, Ko, in order to study the connections between helping and "witnessing 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 classes. We introduce the helping hierarchy whose levels are obtained applying a constant number of times the operator P_{help}() to the set all the languages. We show that the helping hierarchy collapses to the kth level if and only if SH is equal to the kth level. We give characterizations of all the levels and use these to construct a relativizeed world in which the Helping hierarchy is infinite.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
