A cardinality version of Beigel's nonspeedup theorem
From MaRDI portal
Publication:4735186
DOI10.2307/2274739zbMath0685.03034MaRDI QIDQ4735186
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
03D15: Complexity of computation (including implicit computational complexity)
03D30: Other degrees and reducibilities in computability and recursion theory
Related Items
Weak cardinality theorems, The communication complexity of enumeration, elimination, and selection, Index sets and universal numberings, Bounded queries to SAT and the Boolean hierarchy, Learning recursive functions from approximations, Some connections between bounded query classes and non-uniform complexity., On the complexity of finding the chromatic number of a recursive graph. I: The bounded case, Weakly semirecursive sets, Index Sets and Universal Numberings, A proof of Beigel's cardinality conjecture, Frequency computations and the cardinality theorem
Cites Work