Nondeterministic bounded query reducibilities

DOI10.1016/0168-0072(89)90010-9zbMath0673.03025OpenAlexW1987375835MaRDI QIDQ1120564

Richard Beigel, William I. 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

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

Related Items (3)

Weakly semirecursive sets ⋮ On the structures inside truth-table degrees ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

Cites Work

• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Polynomial terse sets
• The complexity of optimization problems
• Terse, superterse, and verbose sets
• On the complexity of unique solutions
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• Semirecursive Sets and Positive Reducibility
• A Theorem on Hypersimple Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Nondeterministic bounded query reducibilities