A proof of Beigel's cardinality conjecture

DOI10.2307/2275299zbMATH Open0763.03025OpenAlexW2160493389WikidataQ122888371 ScholiaQ122888371MaRDI QIDQ4032650FDOQ4032650

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

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

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)

Cites Work

• A generalization of Ramsey's theorem for regular trees
• Frequency computations and the cardinality theorem
• Polynomial terse sets
• Bounded query classes and the difference hierarchy
• A cardinality version of Beigel's nonspeedup theorem
• Bi-immunity results for cheatable 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
• Weak cardinality theorems
• Some connections between bounded query classes and non-uniform complexity.
• On uniform relationships between combinatorial problems
• Choosing, agreeing, and eliminating in communication complexity
• The communication complexity of enumeration, elimination, and selection
• Title not available (Why is that?)
• 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)