Nondeterministic bounded query reducibilities
Richard Beigel, William I. Gasarch, Jim Owings · Annals of Pure and Applied Logic · 1989
A query-bounded Turing machine is an oracle machine which computes its output function from a bounded number of queries to its oracle. In this paper we investigate the behavior of nondeterministic query-bounded Turing machines. In particular we study how easily such machines can compute the function F A n (x 1 , . . . , x n ) from A, where A # N and F A n (x 1 , . . . , x n ) = ##A (x 1 ), . . . , #A (x n )#. We show that each truth-table degree contains a set A such that, F A n can be nondeterministically computed from A by asking at most one question per nondeterministic branch; and that every set of the form A # also has this property. On the other hand, we show that if A is a 1-generic set then F A n cannot be nondeterministically computed from A in less that n queries to A; and that each non-zero r.e. Turing degree contains an r.e. set A with the same property. If the machines involved can only make queries that are part of their input then all sets such that F A n ca...