Polynomial-time oracle machines being restricted to perform a certain search technique in the oracle are considered. These search techniques (e.g. binary search, prefix search) are expressed as monotony properties of the queries computed by the oracle machine. The power of different kinds of restricted machines is systematically investigated. It turns out that restrictions are comparable in different ways if the class of oracles is restricted to NP resp. to sparse sets, or if restricted machines being additionally positive [cf. A.Selman: Reductions on NP and p-selective sets, Theoretical Computer Science 19, pp.287--304, 1982.] are considered.
Back to my homepage