×

On characterizations of randomized computation using plain Kolmogorov complexity. (English) Zbl 1390.68358

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

Citations:

Zbl 1281.68138
PDFBibTeX XMLCite
Full Text: DOI