 |
 |
Eric Allender ; Harry Buhrman ; Luke Friedman ; Bruno Loff - Reductions to the set of random strings: The resource-bounded case
lmcs:723 - Logical Methods in Computer Science, August 19, 2014, Volume 10, Issue 3 - https://doi.org/10.2168/LMCS-10(3:5)2014
; Harry Buhrman ; Luke Friedman ; Bruno Loff
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.
Comment: Conference version in MFCS 2012
- Source : OpenAIRE Graph
- A POSTS PROGRAM FOR COMPLEXITY THEORY; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: SFRH/BD/43169/2008
- Collaborative Research: Understanding, Coping with, and Benefiting from, Intractability; Funder: National Science Foundation; Code: 0832787
- AF: Medium: Computational Complexity Theory and Circuit Complexity; Funder: National Science Foundation; Code: 1064785