Title: Bounded query classes and the difference hierarchy

Authors: Richard Beigel, William Gasarch, and Louise Hay

Abstract: Let A be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible to A based on bounding the number of queries to A that an oracle machine can make. When A is the halting problem K our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracle K.

Download Full Paper