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)

Mathematics Subject Classification ID

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

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)

• 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
• Bounded queries, approximations, and the Boolean hierarchy
• On the computational complexity of querying bounds on differences constraints

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)