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.
2001
262
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11581/7164
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact