DOIAbstract
AbstractA 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 FAn(x1,..., xn) from A, where A ⊆ and FAn(x1,..., xn)=<XA(x1),..., XA〉. We show that each truth-table degree contain s a set A such that FAn can be nondeterministically computed from A by asking at most one question per nondeterministic branch; and that every set of the form Á also has this property. On the other hand, we show that if A is a 1-generic set, then FAn cannot be nondeterministically computed from A in less that n queries to...
Add to ORKG