Terse, superterse, and verbose sets
type: Item
instance of: scholarly article
title: Terse, superterse, and verbose sets
zbMATH Open document ID: 0781.68057
author: Richard Beigel
author: William Gasarch
author: John Gill
author: James C. jun. Owings
published in: Information and Computation
publication date: 1993-06-29T00:00:00Z
review text: If \(f\) is a function and \(A\) is a set then \(f\leq_ TB\) means that \(f\) could be computed with an oracle to \(B\). This paper launches an investigation of how many queries to \(B\) are required. Let \(F^ A_ n(x_ 1,\ldots,x_ n)=\langle\chi_ A(x)_ 1,\ldots,\chi_ A(x_ n)\rangle\), where \(\chi_ A\) is the characteristic function of \(A\). An oracle Turing machine with oracle \(A\) could certainly compute \(F^ A_ n\) with \(n\) queries to \(A\). There are some sets \(A\) (e.g., the halting set) for which \(F^ A_ n\) can be computed with substantially fewer than \(n\) queries. One key reason for this is that the questions asked to the oracle can depend on previous answers, i.e., the questions are adaptive. We examine when it is possible to save queries. We show that the range of possible query savings is limited by the following theorem: \(F^ A_ n\) cannot be computed with only \(\lfloor\log n\rfloor\) queries to a set \(X\) unless \(A\) is recursive. A set \(A\) is terse if the computation of \(F^ A_ n\) from \(A\) requires \(n\) queries. A set \(A\) is superterse if the computation of \(F^ A_ n\) from any set requires \(n\) queries. A set \(A\) is verbose if \(F^ A_{2^ n-1}\) can be computed with \(n\) queries to \(A\). We show the following: (1) a verbose set in each truth-table degree and a superterse set in each nonzero truth-table degree; and (2) an r.e. verbose set in each r.e. truth-table degree and an r.e. terse set in each nonzero r.e. Turing degree.
reviewed by: William Gasarch
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 221544
zbMATH Keywords: decidability
zbMATH Keywords: queries
MaRDI profile type: Publication
full work available at URL: inco.1993.1014
OpenAlex ID: W1995304514
DOI: 10.1006/INCO.1993.1014
description: scientific article; zbMATH DE number 221544