Reductions to the set of random strings: the resource-bounded case
From MaRDI portal
Publication:2878751
DOI10.2168/LMCS-10(3:5)2014zbMATH Open1338.68125arXiv1406.7658OpenAlexW1756533857MaRDI QIDQ2878751FDOQ2878751
Bruno Loff, Harry Buhrman, Luke Friedman, Eric Allender
Publication date: 5 September 2014
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Abstract: This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out in [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it does bear fruit if we consider time-bounded Kolmogorov complexity instead. We show that if a set A is reducible in polynomial time to the set of time-t-bounded Kolmogorov random strings (for all large enough time bounds t), then A is in P/poly, and that if in addition such a reduction exists for any universal Turing machine one uses in the definition of Kolmogorov complexity, then A is in PSPACE.
Full work available at URL: https://arxiv.org/abs/1406.7658
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cited In (8)
- The Complexity of Complexity
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- On the Polynomial Depth of Various Sets of Random Strings
- What can be efficiently reduced to the Kolmogorov-random strings?
- Random strings and truth-table degrees of Turing complete c.e. sets
- Title not available (Why is that?)
- Limits on the Computational Power of Random Strings
- Reduced word enumeration, complexity, and randomization
Recommendations
This page was built for publication: Reductions to the set of random strings: the resource-bounded case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878751)
