Bounded queries in recursion theory (Q1806349): Difference between revisions

An authoritative and very well written account of an interesting field. The description of relative computability in terms of oracles has long been a staple of classical recursion theory and computational complexity theory. However, only in the last 15 years or so have people systematically investigated how many times an oracle needs to be invoked during a computation. For example, let \(\chi_S\) denote the characteristic function of a set \(S\), and let \(K\) denote the halting set. Obviously, given any inputs \((x_1,\ldots,x_{2^n-1})\), one can compute \((\chi_K(x_1),\ldots, \chi_K(x_{2^n-1}))\) by consulting a \(K\)-oracle \(2^n-1\) times. But in fact, a simple algorithm based on binary search can yield the same result with only \(n\) invocations of the oracle. On the other hand, regardless of the set \(Y\), no nonrecursive set \(S\) admits of an algorithm that always computes \((\chi_S(x_1),\ldots,\chi_S(x_{2^n}))\) with only \(n\) calls to an oracle for \(Y\). This book deals with such notions and results, related hierarchies, connections with classical reducibilities (Turing, truth-table, etc.), and much more. The coverage is thorough and up-to-date, and the highly accessible exposition gives a good feel for the field's methods and techniques. The book also features a nice selection of exercises and a 30-page annotated bibliography.