Bounded query classes and the difference hierarchy

DOI10.1007/BF01620618zbMath0663.03032OpenAlexW1990851447MaRDI QIDQ1114678

William I. Gasarch, Richard Beigel, 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 setshierarchy of degreesoracle machineparallel queriesserial queries

Mathematics Subject Classification ID

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

Related Items

A proof of Beigel's cardinality conjecture, Bi-immunity results for cheatable sets, Bounded queries to SAT and the Boolean hierarchy, The Mapmaker's dilemma, On quasilinear-time complexity theory, The complexity of ODD_n^A, On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

Cites Work

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