Bounded query classes and the difference hierarchy

DOI10.1007/BF01620618MaRDI QIDQ1114678zbMATH OpenOpenAlexFDO

Authors Richard Beigel, William Gasarch, Louise Hay

Publication date 1989

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01620618

zbMATH Keywords

halting problemhierarchy of degreeshierarchy of setsoracle machineparallel queriesserial queries

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Review text

Let A be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible to A based on bounding the number of queries to A that an oracle machine can make. When A is the halting problem K our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracle K.

Recommendations

• Bounded Query Classes
• Bounded query rewriting using views
• On a hierarchy of classes for nested databases
• Fragments of Bounded Arithmetic and Bounded Query Classes
• Bounded queries to arbitrary sets
• scientific article; zbMATH DE number 1950753
• On bounded query machines
• Some connections between bounded query classes and non-uniform complexity.
• Query languages for hierarchic databases
• scientific article; zbMATH DE number 1405575

Cites work

• Bi-immunity results for cheatable sets
• Bounded queries to SAT and the Boolean hierarchy
• Convex subsets of \(2^n\) and bounded truth-table reducibility
• Degrees of unsolvability: structure and theory
• Enumeration reducibilities
• Enumeration Reducibility Using Bounded Information: Counting Minimal Covers
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3316891 (Why is no real title available?)
• scientific article; zbMATH DE number 3342830 (Why is no real title available?)
• Limiting recursion
• Polynomial terse sets
• RELATIONSHIPS BETWEEN DIFFERENT FORMS OF RELATIVE COMPUTABILITY OF FUNCTIONS
• Some Notions of Reducibility and Productiveness
• Terse, superterse, and verbose sets
• The Boolean Hierarchy I: Structural Properties
• The difference and truth-table hierarchies for NP
• Trial and error predicates and the solution to a problem of Mostowski

Cited in

(9)

• Nondeterministic bounded query reducibilities
• Bounded queries to SAT and the Boolean hierarchy
• The Mapmaker's dilemma
• Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• A proof of Beigel's cardinality conjecture
• The complexity of ODD_n^A
• On quasilinear-time complexity theory
• Bi-immunity results for cheatable sets

This page was built for publication: Bounded query classes and the difference hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114678)