Reductions to the set of random strings: The resource-bounded case

DOI10.2168/LMCS-10(3:5)2014zbMath1338.68125arXiv1406.7658OpenAlexW1756533857MaRDI QIDQ2878751

Bruno Loff, Harry Buhrman, Luke Friedman, Eric W. Allender

Publication date: 5 September 2014

Published in: Logical Methods in Computer Science, Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (2)

The Complexity of Complexity ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

This page was built for publication: Reductions to the set of random strings: The resource-bounded case