scientific article; zbMATH DE number 1405575

MaRDI QIDQ4938554zbMATH OpenFDO

Authors William Gasarch, Frank Stephan

Publication date 20 September 2000

zbMATH Keywords

surveyverbosenessbounded queriesparallel queriesfrequency computationcomplexity of nonrecursive sets

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On Bounded Queries and Approximation
• Bounded queries, approximations, and the Boolean hierarchy
• On bounded query machines
• Bounded queries to arbitrary sets
• Some connections between bounded query classes and non-uniform complexity.
• Nondeterministic bounded query reducibilities
• Optimization of bound disjunctive queries with constraints
• Bounding queries in the analytic polynomial-time hierarchy
• Bounded queries to SAT and the Boolean hierarchy

Cited in

(10)

• Bounded query classes and the difference hierarchy
• Some initial thoughts on bounded query computations over the reals
• On Bounded Queries and Approximation
• scientific article; zbMATH DE number 845926 (Why is no real title available?)
• Frequency computation and bounded queries
• A proof of Beigel's cardinality conjecture
• Frequency computations and the cardinality theorem
• Quantifying the amount of verboseness
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• scientific article; zbMATH DE number 517081 (Why is no real title available?)

This page was built for publication:

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