Some games on Turing machines and power from random strings

DOI10.1007/978-3-031-36978-0_9OpenAlexW4384789354MaRDI QIDQ6149034

Alexey Milovanov

Publication date: 12 January 2024

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

Full work available at URL: https://doi.org/10.1007/978-3-031-36978-0_9

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Limits on the computational power of random strings
• What can be efficiently reduced to the Kolmogorov-random strings?
• Random strings and tt-degrees of Turing complete C.E. sets
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Kolmogorov Complexity and Algorithmic Randomness
• Unexpected hardness results for Kolmogorov complexity under uniform reductions
• Power from Random Strings

This page was built for publication: Some games on Turing machines and power from random strings