id: 06086213
dt: a
an: 06086213
au: Allender, Eric; Buhrman, Harry; Friedman, Luke; Loff, Bruno
ti: Reductions to the set of random strings: the resource-bounded case.
so: Rovan, Branislav (ed.) et al., Mathematical foundations of computer science
    2012. 37th international symposium, MFCS 2012, Bratislava, Slovakia,
    August 27‒31, 2012. Proceedings. Berlin: Springer (ISBN
    978-3-642-32588-5/pbk). Lecture Notes in Computer Science 7464, 88-99
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-32589-2_11
ab: Summary: This paper is motivated by a conjecture [1,5] 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 [5] 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.
rv: