Bounded queries in recursion theory
type: Item
instance of: scholarly article
title: Bounded queries in recursion theory
zbMATH Open document ID: 0936.03038
author: William Gasarch
author: Georgia A. Martin
published in: Progress in Computer Science and Applied Logic
publication date: 1999-11-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03-02
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1356677
zbMATH Keywords: query
zbMATH Keywords: oracle
zbMATH Keywords: terse
zbMATH Keywords: verbose
zbMATH Keywords: supportive
zbMATH Keywords: subjective
zbMATH Keywords: relative computability
zbMATH Keywords: computational complexity
zbMATH Keywords: hierarchies
zbMATH Keywords: reducibilities
reviewed by: Leon Harkleroad
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1356677