Limits on the Computational Power of Random Strings

DOI10.1007/978-3-642-22006-7_25MaRDI QIDQ3012814zbMATH OpenOpenAlexFDO

Authors Luke Friedman, Eric Allender, William Gasarch

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Limits on the computational power of random strings
• On the computational power of random strings
• On the complexity of random strings
• Limitations of efficient reducibility to the Kolmogorov random strings
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• Power of randomization in automata on infinite strings
• Power of Randomization in Automata on Infinite Strings
• Limit probabilities for random sparse bit strings

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• An introduction to Kolmogorov complexity and its applications
• An observation on probability versus randomness with applications to complexity classes
• Circuit minimization problem
• Kolmogorov entropy in the context of computability theory
• Limitations of Hardness vs. Randomness under Uniform Reductions
• Limits on the computational power of random strings
• Lower bounds for reducibility to the Kolmogorov random strings
• On Languages Reducible to Algorithmically Random Languages
• On the robustness of ALMOST-$\mathcal {R}$
• Power from Random Strings
• Pseudorandomness and average-case complexity via uniform reductions
• Randomness vs time: Derandomization under a uniform assumption
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Theory of Cryptography
• What can be efficiently reduced to the Kolmogorov-random strings?

Cited in

(20)

• Limits on the computational power of random strings
• On the computational power of random strings
• Random access to advice strings and collapsing results
• Randomness is hard
• Randomness, computation and mathematics
• On characterizations of randomized computation using plain Kolmogorov complexity
• Closure of resource-bounded randomness notions under polynomial-time permutations
• Lower bounds for reducibility to the Kolmogorov random strings
• scientific article; zbMATH DE number 1335898 (Why is no real title available?)
• scientific article; zbMATH DE number 2081089 (Why is no real title available?)
• On characterizations of randomized computation using plain Kolmogorov complexity
• Limitations of efficient reducibility to the Kolmogorov random strings
• Unexpected hardness results for Kolmogorov complexity under uniform reductions
• STACS 2004
• Kolmogorov complexity, circuits, and the strength of formal theories of arithmetic
• Power from Random Strings
• Algorithms and Computation
• Power of Randomization in Automata on Infinite Strings
• Some games on Turing machines and power from random strings
• A simple storage scheme for strings achieving entropy bounds

This page was built for publication: Limits on the Computational Power of Random Strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012814)