Name
Abstract | ||
|---|---|---|
We discuss two notions of functional oracle for logarithmic space-bounded machines, which differ in whether there is only one oracle tape for both the query and the answer or a separate tape for the answer, which can still be read while the next query is already being constructed. The first notion turns out to be basically nonadaptive, behaving like access to an oracle set. The second notion, on the other hand, is adaptive. By imposing appropriate bounds on the number of functional oracle queries made in this computation model, we obtain new characterizations of the NC and AC hierarchies; thus the number of oracle queries can be considered as a measure of parallel time. Using this characterization of parallel classes, we solve open questions of Wilson. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/BF01191473 | Mathematical Systems Theory |
Keywords | Field | DocType |
Computation Model,Computational Mathematic,Parallel Classis,Parallel Time,Oracle Query | Discrete mathematics,Combinatorics,Oracle,Random oracle,Theoretical computer science,Logarithm,Hierarchy,Mathematics,Computation | Journal |
Volume | Issue | ISSN |
28 | 2 | 0025-5661 |
Citations | PageRank | References |
7 | 0.79 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carme Àlvarez | 1 | 316 | 28.75 |
| José L. Balcázar | 2 | 701 | 62.06 |
| Birgit Jenner | 3 | 247 | 14.47 |