Limits on the Computational Power of Random Strings
From MaRDI portal
Publication:3012814
DOI10.1007/978-3-642-22006-7_25zbMath1332.68095OpenAlexW190215904MaRDI QIDQ3012814
Luke Friedman, William I. Gasarch, Eric W. Allender
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_25
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Randomness vs time: Derandomization under a uniform assumption
- Limits on the computational power of random strings
- Pseudorandomness and average-case complexity via uniform reductions
- What can be efficiently reduced to the Kolmogorov-random strings?
- Circuit minimization problem
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Lower Bounds for Reducibility to the Kolmogorov Random Strings
- An observation on probability versus randomness with applications to complexity classes
- On Languages Reducible to Algorithmically Random Languages
- On the robustness of ALMOST-$\mathcal {R}$
- Power from Random Strings
- An introduction to Kolmogorov complexity and its applications
- Theory of Cryptography
- Kolmogorov entropy in the context of computability theory
This page was built for publication: Limits on the Computational Power of Random Strings
