Logical Approaches to Computational Barriers

DOI10.1007/11780342zbMath1145.03325arXivcs/0511074OpenAlexW4255986326WikidataQ55968647 ScholiaQ55968647MaRDI QIDQ5898813

David Doty

Publication date: 30 April 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0511074

zbMATH Keywords

Kolmogorov complexitycompressionmartingalerandom sequenceTuring reductionConstructive dimension

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers ⋮ Optimal redundancy in computations from random oracles ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ Pushdown dimension ⋮ Constructive dimension and Turing degrees ⋮ Dimension extractors and optimal decompression