Hirahara, Shuichi; Kawamura, Akitoshi On characterizations of randomized computation using plain Kolmogorov complexity. (English) Zbl 1390.68358 Computability 7, No. 1, 45-56 (2018). Summary: E. Allender et al. [Inf. Comput. 222, 80–92 (2013; Zbl 1281.68138)] recently proved an upper bound of PSPACE for the class \(\mathrm{DTTR}_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}_K\) in fact lies closer to BPP, a lower bound established earlier by H. Buhrman et al. [“Derandomizing from random strings”, in: Proceedings of the 25th annual IEEE conference on computational complexity, CCC’15. Los Alamitos, CA: IEEE Computer Society. 58–63 (2015; doi:10.1109/CCC.2010.15)]. It is also conjectured that we have similar bounds for the analogous class \(\mathrm{DTTR}_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}_C\) sits between BPP and \(\mathrm{PSPACE}\cap\mathrm{P/poly}\). Next, we show that the class \(\mathrm{DTTR}_{C,\alpha}\) obtained from \(\mathrm{DTTR}_C\) by imposing a super-constant minimum query length restriction on the reduction lies between BPP and PSPACE. Finally, we show that the class \(\mathrm{P}/R_{C^t}^{=\log}\) obtained by further restricting the reduction to ask queries of logarithmic length lies between BPP and \(\Sigma_2^p\cap\mathrm{P/poly}\). MSC: 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68W20 Randomized algorithms Keywords:Kolmogorov complexity; randomness; truth-table reductions Citations:Zbl 1281.68138 PDFBibTeX XMLCite \textit{S. Hirahara} and \textit{A. Kawamura}, Computability 7, No. 1, 45--56 (2018; Zbl 1390.68358) Full Text: DOI