On Bounded Queries and Approximation

DOI10.1137/S0097539794266481MaRDI QIDQ4337440zbMATH OpenFDO

Authors Richard Chang, William Gasarch, C. Lund

Publication date 3 August 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539794266481

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Bounded queries, approximations, and the Boolean hierarchy
• scientific article; zbMATH DE number 1405575
• Bounding queries in the analytic polynomial-time hierarchy
• On bounded query machines
• Bounded queries to arbitrary sets
• On the Structure of Bounded Queries to Arbitrary NP Sets
• Some connections between bounded query classes and non-uniform complexity.
• Some initial thoughts on bounded query computations over the reals
• Nondeterministic bounded query reducibilities
• Bounded queries in recursion theory

Cited in

(6)

• Bounded queries, approximations, and the Boolean hierarchy
• On the computational complexity of querying bounds on differences constraints
• scientific article; zbMATH DE number 1860650 (Why is no real title available?)
• scientific article; zbMATH DE number 1405575 (Why is no real title available?)
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• Structure in approximation classes

This page was built for publication: On Bounded Queries and Approximation

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