A Note on Query: Solving the Missing Case

by    Harald Hempel

Preprint series: 99-29, Reports on Computer Science

Abstract:
We show that the order in which different-size-rounds of parallel
queries to oracles from the polynomial hierarchy are made never
matters. This solves a problem left open by previous papers in that
area.
Our results shed new light on the number-of-queries tradeoffs between
parallel, a mixture of parallel and sequential, and pure sequential
access to oracles from the polynomial hierarchy.

Upload: 1999-05-26

Update: 1999-05-26


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.