A cardinality version of Beigel's nonspeedup theorem

DOI10.2307/2274739zbMath0685.03034OpenAlexW2040234790MaRDI QIDQ4735186

James C. jun. Owings

Publication date: 1989

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

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

zbMATH Keywords

relative computabilityhalting set

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Learning recursive functions from approximations, Weakly semirecursive sets, A proof of Beigel's cardinality conjecture, Frequency computations and the cardinality theorem, Some connections between bounded query classes and non-uniform complexity., Bounded queries to SAT and the Boolean hierarchy, Weak cardinality theorems, Index Sets and Universal Numberings, Index sets and universal numberings, The communication complexity of enumeration, elimination, and selection, On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

Cites Work

• Unnamed Item
• Members of countable \(\Pi ^ 0_ 1\) classes
• Set theory. An introduction to independence proofs