On Bounded Queries and Approximation

DOI10.1137/S0097539794266481zbMATH Open0868.68067MaRDI QIDQ4337440FDOQ4337440

Richard Chang, C. Lund, William Gasarch

Publication date: 3 August 1997

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

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

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)

Cited In (6)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the computational complexity of querying bounds on differences constraints
• Structure in approximation classes
• Title not available (Why is that?)
• Bounded queries, approximations, and the Boolean hierarchy

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)