A proof of Beigel's cardinality conjecture

DOI10.2307/2275299MaRDI QIDQ4032650zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 1 April 1993

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275299

zbMATH Keywords

query complexitydecidabilityrecursive functionsoracle machinesbounded query classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• Effective Search Problems
• Publication:4864470
• Terse, superterse, and verbose sets
• scientific article; zbMATH DE number 1405575
• Some connections between bounded query classes and non-uniform complexity.
• Frequency computation and bounded queries
• scientific article; zbMATH DE number 1114037
• scientific article; zbMATH DE number 512828
• Quantifying the amount of verboseness
• scientific article; zbMATH DE number 1678392

Cites work

• A cardinality version of Beigel's nonspeedup theorem
• A generalization of Ramsey's theorem for regular trees
• Bi-immunity results for cheatable sets
• Bounded query classes and the difference hierarchy
• Frequency computations and the cardinality theorem
• Polynomial terse sets

Cited in

(22)

• A cardinality version of Beigel's nonspeedup theorem
• One query reducibilities between partial information classes
• Index sets and universal numberings
• On polynomially \(\mathcal{D}\)-verbose sets
• Resource bounded frequency computations with three errors
• The power of frequency computation
• Index sets and universal numberings
• Binary search and recursive graph problems
• Some connections between bounded query classes and non-uniform complexity.
• Weak cardinality theorems
• On uniform relationships between combinatorial problems
• Choosing, agreeing, and eliminating in communication complexity
• The communication complexity of enumeration, elimination, and selection
• scientific article; zbMATH DE number 845926 (Why is no real title available?)
• Frequency computation and bounded queries
• Frequency computations and the cardinality theorem
• Learning recursive functions from approximations
• Enumerations including laconic enumerators
• Computable categoricity and the Ershov hierarchy
• Resource Bounded Frequency Computations with Three Errors
• On the influence of technology on learning processes
• Extremes in the degrees of inferability

This page was built for publication: A proof of Beigel's cardinality conjecture

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