Resource bounded Kučera–Gács Theorems

Satyadev Nandakumar, Akhil S, Chandra Shekhar Tiwari · 2026

Read Resource bounded Kučera–Gács Theorems by Satyadev Nandakumar, Akhil S, Chandra Shekhar Tiwari (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21546.txt.

Introduction

Satyadev Nandakumar, Akhil S, and Chandra Shekhar Tiwari study resource-bounded Kučera-Gács theorems. The Kučera-Gács theorem states that every infinite sequence X is Turing reducible to a Martin-Löf random sequence R. They study resource-bounded analogues at polynomial-time and finite-state bounds. They prove a quasi-polynomial-time theorem: every X is quasi-polynomial-time reducible to a polynomial-time random R, with oracle use n plus little-o of n bits for n bits of X.

Catalog record

CREATORSatyadev Nandakumar, Akhil S, Chandra Shekhar Tiwari
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60442
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21546

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Resource bounded Kučera–Gács Theorems Satyadev Nandakumar, Akhil S, Chandra Shekhar Tiwari Abstract The Kučera–Gács theorem [ 12 ] [ 9 ] is a fundamental result in algorithmic randomness. It states that every infinite sequence X X is Turing reducible to a Martin-Löf random R 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 X is quasi-polynomial-time reducible to a polynomial-time random sequence R R . We also show that for any X X , the oracle use of R R is n + o ⁡ ( n ) n+o(n) bits for obtaining the first n n bits of X X . We then study the relationship between compressibility and Turing reductions, in the polynomial-time setting. We establish that ρ 𝗉𝗈𝗅𝗒 − ​ ( X ) = 𝒦 𝗉𝗈𝗅𝗒 ​ ( X ) \rho^{-}_{\mathsf{poly}}(X)=\mathcal{K}_{\mathsf{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 ( dim P {\mathrm{dim}}_{\mathrm{P}} ) if one-way functions exist, resolving an open problem from Doty’s [ 7 ] work. We use these results to strengthen the quasi-polynomial-time Kučera-Gács Theorem. We show that every infinite sequence X X is quasi-polynomial-time reducible to a polynomial-time random sequence R R , where the lower oracle use rate of the reduction is less than 𝒦 𝗉𝗈𝗅𝗒 ​ ( X ) \mathcal{K}_{\mathsf{poly}}(X) . We also establish a lower bound for how powerful the reduction needs to be if we have to extract any sequence from randoms. We show that any sequence extracted from the (even larger) set of 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 fails for finite-state reductions. 1 Introduction There is a fundamental dichotomy between structure and randomness. Kolmogorov utilized computability theory to provide a new foundation for information and probability theory by introducing the concept of an “individual random string”. His key insight was to use incompressibility as a basis for randomness, after fixing a universal mode of description-algorithms. Kolmogorov defined a finite string x to be incompressible if the shortest program that outputs x is at least as long as x itself. Martin-Löf extended this approach to define an individual random infinite sequence. This concept is robust - it has equivalent definitions using constructive measure theory, unpredictability, compressibility, betting (martingales), and others (see, for example, Downey, Hirschfeldt [ 8 ] , and Nies [ 19 ] ). A striking phenomenon emerges when we examine how Martin-Löf randoms interact with Turing reducibility. Independently, Kučera [ 12 ] and Gács [ 9 ] show that every infinite sequence X is Turing reducible to a Martin-Löf random R . This result has led to a rich literature studying the interplay between the strength of reductions and notions of randomness. Gács’ original result [ 9 ] had a redundancy of o(n) , with n+\sqrt{n}\log(n) oracle usage to determine the first n bits of X in the reduction. Downey and Hirschfeldt [ 8 ] show that we cannot improve this to n+O(1) . Doty [ 7 ] established a deep connection between the oracle usage and the effective Hausdorff dimension - informally, the information rate - of X , showing that the latter is precisely characterized by the oracle usage in the Kučera–Gács theorem. Resource-bounded reducibilities have also been studied. Book, Lutz and Wagner [ 4 ] show that the characteristic sequence of a decidable language L is polynomial-time reducible to Martin-Löf randoms if and only if L\in{\rm BPP} . Thus, not every sequence is polynomial-time reducible to a Martin-Löf random. This naturally raises the question: does an analogue of the Kučera–Gács theorem hold when both randomness and reducibility are restricted by feasible computation? Doty [ 7 ] shows that his characterization of dimension also extends to the oracle use in {\rm PSPACE} -bounded reducibility to {\rm PSPACE} randoms, and establishes a one-sided inequality for polynomial-time. However, the converse for polynomial-time reduction remained open. In this work, we resolve this gap. We first show that every sequence is quasi-polynomial-time reducible to some polynomial-time random. Moreover, the reduction uses only n+o(n) oracle bits to compute the first n bits of the sequence. We then characterize one notion of polynomial-time dimension, namely, that using time-bounded Kolmogorov complexity rate using polynomial-time reductions to some (not necessarily random) sequence. In a recent work, Akhil, Nandakumar, Pulari and Sarma [ 18 ] establish that notions of polynomial-time dimension using betting algorithms called gales and that using Kolmogorov complexity rates are inequivalent in polynomial-time, if cryptographic one-way functions exist. Thus Doty’s theorem does not extend to polynomial-time dimension if one-way functions exist, even though we obtain an alternate characterization using Kolmogorov complexity rates. We also establish a lower bound for how powerful the reduction needs to be if we have to extract any sequence from randoms. We show that for finite-state reductions between infinite sequences, even when we weaken the notion of randomness to include all normal sequences (sequences where every finite string w appears with asymptotic frequency 2^{-|w|} ), we cannot extract every sequence. We establish an invariant property maintained by finite-state reductions: if X is finite-state reducible to a normal sequence N , then X must have a well-defined asymptotic frequency for all letters. But, it is easy to construct sequences where the asymptotic frequency of a letter is undefined. Hence, such sequences cannot be finite-state reducible to a normal sequence (and a fortiori , to polynomial-time randoms). 1.1 Our contributions. This work studies the extent to which the Kučera–Gács theorem persists under computational resource bounds, with a particular focus on polynomial-time and finite-state reducibilities. We obtain the following results. • Quasi-polynomial-time Kučera–Gács. We show that for every infinite sequence X there exists a polynomial-time random sequence R such that X is computable from R via a quasi-polynomial-time reduction. Moreover, only u_{n}=n+o(n) bits of the random oracle R are required to compute the first n bits of any given sequence X . • Polynomial-time decompression ratio characterisation. We establish that the lower polynomial-time decompression ratio \rho^{-}_{\mathsf{poly}} coincides with the polynomial-time Kolmogorov complexity rate \mathcal{K}_{\mathsf{poly}} . We show that \rho^{-}_{\mathsf{poly}} and polynomial-time dimension {\mathrm{dim}}_{\mathrm{P}} are not equal in general, under the assumption that one-way functions exist. This resolves an open question from Doty [ 7 ] . • Dimension-sensitive Kučera–Gács. We further strengthen the quasi-polynomial-time Kučera–Gács theorem by showing that the oracle rate use can be bounded by the \mathcal{K}_{\mathsf{poly}} dimension of the sequence, that is, \liminf_{n\to\infty}u_{n}/n\leq\mathcal{K}_{\mathsf{poly}}(X) . • No Kučera–Gács for finite-state reductions. We show that no analogue of the Kučera–Gács theorem holds for finite-state reductions. Even when we start from the set of normal numbers (the weakest notion of randomness), the sequences generated by a finite-state reduction must have well-defined limiting symbol frequencies, and therefore cannot generate all sequences. 2 Preliminaries 2.1 Notation \mathbb{N} denotes the set of natural numbers, \mathbb{Q} denotes the set of rationals, and \mathbb{R} denotes the set of real numbers.

Read the complete text