On characterizations of randomized computation using plain Kolmogorov complexity 1

Abstract

Allender, Friedman, and Gasarch recently proved an upper bound of $\mathrm{PSPACE}$ for the class ${\mathrm{DTTR}}_{\mathit{K}}$ of decidable languages that are polynomial-time truth-table reducible to the set of prefix-free Kolmogorov-random strings regardless of the universal machine used in the definition of Kolmogorov complexity. It is conjectured that ${\mathrm{DTTR}}_{\mathit{K}}$ in fact lies closer to $\mathrm{BPP}$ , a lower bound established earlier by Buhrman, Fortnow, Koucký, and Loff. It is also conjectured that we have similar bounds for the analogous class ${\mathrm{DTTR}}_{\mathit{C}}$ defined by plain Kolmogorov randomness. In this paper, we provide further evidence for these conjectures. First, we show that the time-bounded analogue of ${\mathrm{DTTR}}_{\mathit{C}}$ sits between $\mathrm{BPP}$ and $\mathrm{PSPACE}\cap \mathrm{P}\mathrm{/}\mathrm{poly}$ . Next, we show that the class ${\mathrm{DTTR}}_{\mathit{C}\mathrm{,}\mathit{\alpha }}$ obtained from ${\mathrm{DTTR}}_{\mathit{C}}$ by imposing a super-constant minimum query length restriction on the reduction lies between $\mathrm{BPP}$ and $\mathrm{PSPACE}$ . Finally, we show that the class $\mathrm{P}\mathrm{/}{\mathit{R}}_{{\mathit{C}}^{\mathit{t}}}^{=log}$ obtained by further restricting the reduction to ask queries of logarithmic length lies between $\mathrm{BPP}$ and ${\mathrm{\Sigma }}_2^{\mathit{p}}\cap \mathrm{P}\mathrm{/}\mathrm{poly}$ .