Resource bounded Kučera-Gács Theorems

Abstract

The Kučera--Gács theorem is a fundamental result in algorithmic randomness. It states that every infinite sequence $X$ is Turing reducible to a Martin-Löf random $R$. This paper studies resource-bounded analogues of the Kučera-Gács Theorem, at the resource bounds of polynomial-time and finite-state computation. We prove a {quasi-polynomial-time}{ Kučera-Gács Theorem}, showing that every infinite sequence $X$ is quasi-polynomial-time reducible to a \emph{polynomial-time random} sequence $R$. We also show that for any $X$, the oracle use of $R$ is $n+o(n)$ bits for obtaining the first $n$ bits of $X$. We then study the relationship between compressibility and Turing reductions, in the polynomial-time setting. We establish that $\ddot{I}{}_{\mathsf{poly}}^{-}(X)=K_{poly}(X)$, demonstrating that the lower polynomial-time Turing decompression ratio is precisely characterized by the polynomial-time Kolmogorov complexity rate. We note that this characterization fails for the polynomial-time dimension if one-way functions exist, resolving an open problem from Doty's work. We use these results to strengthen the {quasi-polynomial-time}{ Kučera-Gács Theorem}. We show that every infinite sequence $X$ is quasi-polynomial-time reducible to a {polynomial-time random} sequence $R$, where the lower oracle use rate of the reduction is less than $K_{poly}(X)$. We also show that any sequence extracted from the (even larger) set of \emph{normal sequences} by a finite-state reduction must have a convergent asymptotic frequency for its symbols. Since sequences lacking this invariant property exist, they cannot be finite-state reduced from any normal sequence. Hence we show that the Kučera-Gács theorem \emph{fails} for finite-state reductions.