A proof of Beigel's cardinality conjecture

DOI10.2307/2275299zbMath0763.03025WikidataQ122888371 ScholiaQ122888371MaRDI QIDQ4032650

No author found.

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

decidability; recursive functions; query complexity; oracle machines; bounded query classes

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

03D20: Recursive functions and relations, subrecursive hierarchies

Related Items

The communication complexity of enumeration, elimination, and selection, Frequency computation and bounded queries, Index sets and universal numberings, Choosing, agreeing, and eliminating in communication complexity, Resource bounded frequency computations with three errors, Computable categoricity and the Ershov hierarchy, Extremes in the degrees of inferability, Learning recursive functions from approximations, Binary search and recursive graph problems, Some connections between bounded query classes and non-uniform complexity., Enumerations including laconic enumerators, One query reducibilities between partial information classes, On uniform relationships between combinatorial problems, On the Influence of Technology on Learning Processes, Resource Bounded Frequency Computations with Three Errors, Index Sets and Universal Numberings

Cites Work

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