Nondeterministic bounded query reducibilities

DOI10.1016/0168-0072(89)90010-9MaRDI QIDQ1120564zbMATH OpenOpenAlexFDO

Authors Richard Beigel, William Gasarch, James C. jun. Owings

Publication date 1989

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(89)90010-9

zbMATH Keywords

Turing degreetruth-table degreebounded number of calls to the oraclenondeterministic oracle machinesobjective setsubjective set

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• The complexity of ODD_n^A
• On relativized nondeterministic polynomial-time bounded computations
• On adaptive versus nonadaptive bounded query machines
• Bounded query classes and the difference hierarchy
• Bounded queries to SAT and the Boolean hierarchy

Cites work

• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 4024790 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Theorem on Hypersimple Sets
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• On the complexity of unique solutions
• Polynomial terse sets
• Semirecursive Sets and Positive Reducibility
• Terse, superterse, and verbose sets
• The complexity of optimization problems

Cited in

(8)

• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• scientific article; zbMATH DE number 1405575 (Why is no real title available?)
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• On the computational complexity of querying bounds on differences constraints
• On Bounded Queries and Approximation
• Weakly semirecursive sets
• On the structures inside truth-table degrees

This page was built for publication: Nondeterministic bounded query reducibilities

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