On characterizations of randomized computation using plain Kolmogorov complexity
Shuichi Hirahara, Akitoshi Kawamura · Computability · 2017
Allender, Friedman, and Gasarch recently proved an upper bound of [Formula: see text] for the class [Formula: see text] 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 [Formula: see text] in fact lies closer to [Formula: see text], a lower bound established earlier by Buhrman, Fortnow, Koucký, and Loff. It is also conjectured that we have similar bounds for the analogous class [Formula: see text] defined by plain Kolmogorov randomness. In this paper, we provide further evidence for these conjectures. First, we show that the time-bounded analogue of [Formula: see text] sits between [Formula: see text] and [Formula: see text]. Next, we show that the class [Formula: see text] obtained from [Formula: see text] by imposing a super-constant minimum query length restriction on the reduction lies between [Formula: see text] and [Formula: see text]. Finally, we show that the class [Formula: see text] obtained by further restricting the reduction to ask queries of logarithmic length lies between [Formula: see text] and [Formula: see text].