Limits on the computational power of random strings

DOI10.1016/j.ic.2011.09.008zbMath1281.68138OpenAlexW2068163639MaRDI QIDQ1951574

Eric W. Allender, Luke Friedman, William I. Gasarch

Publication date: 6 June 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.09.008

zbMATH Keywords

Kolmogorov complexitycomplexity classesprefix complexityuniform derandomization

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (7)

A MINIMAL SET LOW FOR SPEED ⋮ On Low for Speed Oracles ⋮ Some games on Turing machines and power from random strings ⋮ The Complexity of Complexity ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Limits on the Computational Power of Random Strings ⋮ On low for speed oracles

This page was built for publication: Limits on the computational power of random strings