Name
Abstract | ||
|---|---|---|
Schoning [14] introduced a notion of helping and suggested the study of the class P-help( C) of the languages that can be helped by oracles in a given class 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 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 P-help(.) 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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1051/ita:2001101 | RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS |
Field | DocType | Volume |
Combinatorics,Formal language,Existential quantification,Computer science,P,Oracle,Operator (computer programming),If and only if,Time complexity,Hierarchy | Journal | 35 |
Issue | Citations | PageRank |
4 | 0 | 0.34 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrizio Cintioli | 1 | 7 | 2.68 |
| Riccardo Silvestri | 2 | 1324 | 90.84 |