Bounded queries in recursion theory
computational complexityhierarchiesoraclequeryreducibilitiesrelative computabilitysubjectivesupportiveterseverbose
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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.
- Some connections between bounded query classes and non-uniform complexity.
- On the query complexity of finding a local maximum point.
- Recursive properties of branching and BGG resolution
- Learning and classifying
- On the convergence of query-bounded computations and logical closure properties of c.e. sets
- On Bounded Queries and Approximation
- scientific article; zbMATH DE number 1953141 (Why is no real title available?)
- Abstract recursion and intrinsic complexity
- Some initial thoughts on bounded query computations over the reals
- The complexity of ODDnA
- Weak cardinality theorems
- The communication complexity of enumeration, elimination, and selection
- Frequency computation and bounded queries
- Choosing, agreeing, and eliminating in communication complexity
- The complexity of finding SUBSEQ(A)
This page was built for publication: Bounded queries in recursion theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1806349)
