Resource bounded Kučera-Gács Theorems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910242238889984 |
|---|---|
| author | Nandakumar, Satyadev S, Akhil Tiwari, Chandra Shekhar |
| author_facet | Nandakumar, Satyadev S, Akhil Tiwari, Chandra Shekhar |
| contents | 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 $ρ^-_{\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21546 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Resource bounded Kučera-Gács Theorems Nandakumar, Satyadev S, Akhil Tiwari, Chandra Shekhar Computational Complexity Information Theory 03D32, 68P30 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 $ρ^-_{\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. |
| title | Resource bounded Kučera-Gács Theorems |
| topic | Computational Complexity Information Theory 03D32, 68P30 |
| url | https://arxiv.org/abs/2605.21546 |