scientific article; zbMATH DE number 1405575
From MaRDI portal
Publication:4938554
The present work gives an overview on the field of bounded queries in recursion theory including the subfields of frequency computation and verboseness. The main topic is finding quantitative notions for the complexity of nonrecursive sets in terms of the local complexity of computing the \(n\)-fold characteristic function. This work presents in particular the various proof methods popular in this field. For the entire collection see [Zbl 0919.00039].
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
(12)- Bounded query classes and the difference hierarchy
- Bounded queries in recursion theory
- Quantifying the amount of verboseness
- A proof of Beigel's cardinality conjecture
- Frequency computations and the cardinality theorem
- scientific article; zbMATH DE number 517081 (Why is no real title available?)
- On Bounded Queries and Approximation
- scientific article; zbMATH DE number 845926 (Why is no real title available?)
- Some initial thoughts on bounded query computations over the reals
- Open least element principle and bounded query computation
- Frequency computation and bounded queries
- Complexities of effective reductions with ordinal Turing machines
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)
