pith. sign in

arxiv: 2605.21546 · v1 · pith:4PH3VZKMnew · submitted 2026-05-20 · 💻 cs.CC · cs.IT· math.IT

Resource bounded Kuv{c}era-G\'{a}cs Theorems

Satyadev Nandakumar , Akhil S , Chandra Shekhar Tiwari This is my paper

Pith reviewed 2026-05-22 01:08 UTC · model grok-4.3

classification 💻 cs.CC cs.ITmath.IT
keywords algorithmic randomnessKučera-Gács theorempolynomial-time reductionsKolmogorov complexityfinite-state transducersnormal sequencesTuring reducibilityquasi-polynomial time
4
0 comments X

The pith

Every infinite sequence is quasi-polynomial-time reducible to a polynomial-time random sequence with n plus little-o-n oracle bits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops resource-bounded versions of the classical Kučera-Gács theorem from algorithmic randomness. It proves that any infinite sequence X can be recovered from a polynomial-time random sequence R by a quasi-polynomial-time Turing reduction that consults only n + o(n) bits of R to produce the first n bits of X. The work further shows that the lower polynomial-time Turing decompression ratio of X equals its polynomial-time Kolmogorov complexity rate, and uses this equality to tighten the quasi-polynomial reduction bound. Finally, it demonstrates that the theorem fails entirely at the finite-state level because finite-state reductions from normal sequences must preserve convergent asymptotic symbol frequencies, a property not shared by all sequences.

Core claim

The authors prove a quasi-polynomial-time Kučera-Gács theorem: every infinite sequence X is quasi-polynomial-time reducible to some polynomial-time random sequence R, with oracle use of only n + o(n) bits on inputs of length n. They establish the equality ρ⁻_poly(X) = K_poly(X) for any X, which strengthens the reduction so that the lower oracle-use rate is strictly less than K_poly(X). They also prove that the corresponding statement is false for finite-state reductions, since any sequence obtained from a normal sequence via a finite-state transducer must possess a convergent asymptotic frequency for each symbol.

What carries the argument

Quasi-polynomial-time Turing reduction to a polynomial-time random sequence, together with the equality between the lower polynomial-time Turing decompression ratio and polynomial-time Kolmogorov complexity rate.

If this is right

  • Any sequence X can be obtained from a polynomial-time random oracle by a quasi-polynomial-time procedure using only n + o(n) oracle bits.
  • The lower polynomial-time Turing decompression ratio of any sequence equals its polynomial-time Kolmogorov complexity rate.
  • If one-way functions exist, the same equality does not hold when polynomial-time dimension is substituted for Kolmogorov complexity.
  • Finite-state reductions from normal sequences always produce sequences with convergent symbol frequencies.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Resource-bounded randomness notions can be separated by the power of the reductions that connect them.
  • The failure at finite-state level suggests that frequency preservation is a robust invariant that distinguishes finite-state computation from Turing computation even in the presence of randomness.
  • The n + o(n) oracle-use bound indicates that the information transfer remains close to linear even after the time bound is relaxed to quasi-polynomial.

Load-bearing premise

Polynomial-time random sequences exist and the definitions of these sequences and of normal sequences remain stable enough for the stated reductions and frequency-preservation properties to hold at the given resource bounds.

What would settle it

An explicit infinite sequence X for which the lower polynomial-time Turing decompression ratio differs from its polynomial-time Kolmogorov complexity rate, or a finite-state reduction that maps some normal sequence to a sequence lacking convergent asymptotic frequencies.

read the original abstract

The Ku\v{c}era--G\'{a}cs theorem is a fundamental result in algorithmic randomness. It states that every infinite sequence $X$ is Turing reducible to a Martin-L\"of random $R$. This paper studies resource-bounded analogues of the Ku\v{c}era-G\'acs Theorem, at the resource bounds of polynomial-time and finite-state computation. We prove a {quasi-polynomial-time}{ Ku\v{c}era-G\'acs 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 $\rho^-_{\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\v{c}era-G\'acs 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\v{c}era-G\'acs theorem \emph{fails} for finite-state reductions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript establishes resource-bounded analogues of the Kučera-Gács theorem. It proves that every infinite sequence X is quasi-polynomial-time reducible to a polynomial-time random sequence R with n+o(n) oracle use. It shows ρ⁻_poly(X) = K_poly(X) and that this characterization fails for polynomial-time dimension assuming one-way functions exist, resolving an open question. The quasi-polynomial result is strengthened to oracle-use rate strictly less than K_poly(X). It further shows that the Kučera-Gács theorem fails for finite-state reductions, as finite-state reductions from normal sequences preserve asymptotic symbol frequencies, a property not shared by all sequences.

Significance. If the results hold, the work makes a solid contribution to resource-bounded algorithmic randomness by adapting the classical Kučera-Gács construction to quasi-polynomial time while preserving polynomial-time randomness and controlling oracle use. The equality ρ⁻_poly(X) = K_poly(X) provides a clean characterization, and the conditional separation for dimension resolves a prior open problem. The explicit constructions, the direct counterexample via frequency preservation for finite-state reductions, and the use of standard definitions of polynomial-time randomness are strengths that support the central claims.

minor comments (2)
  1. The introduction would benefit from a brief paragraph explicitly contrasting the new quasi-polynomial construction with the classical Kučera-Gács argument to clarify which steps are adapted for the resource bound.
  2. Notation for the lower decompression ratio ρ⁻_poly and the Kolmogorov rate K_poly is introduced without a dedicated preliminary subsection; a short definitions paragraph would improve readability for readers outside the immediate subfield.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript and the recommendation for minor revision. No specific major comments appear in the report, so we have no individual points requiring detailed rebuttal at this stage. We will make appropriate minor revisions to the manuscript as directed by the editor.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via explicit constructions

full rationale

The paper adapts the classical Kučera-Gács theorem via explicit constructions to quasi-polynomial-time reductions while preserving polynomial-time randomness of the target sequence R (with n+o(n) oracle use), and establishes ρ⁻_poly(X) = K_poly(X) by directly relating decompression ratios to polynomial-time Kolmogorov complexity rates. The finite-state failure follows from the independent frequency-preservation property of normal sequences, which is an external invariant. No self-definitional reductions, fitted parameters renamed as predictions, load-bearing self-citations, or smuggled ansatzes appear; the work resolves an open question from Doty's external prior work. All steps rest on standard definitions of randomness and reducibility without reducing the claims to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard definitions from algorithmic randomness and complexity theory drawn from prior literature; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard definitions of Turing reducibility, Martin-Löf randomness, polynomial-time randomness, and normal sequences
    The paper invokes these foundational notions to state the resource-bounded analogues.
  • domain assumption Existence of polynomial-time random sequences suitable for use as oracles
    Required for the quasi-polynomial-time reduction statements to be meaningful.

pith-pipeline@v0.9.0 · 5909 in / 1510 out tokens · 70723 ms · 2026-05-22T01:08:05.162874+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Klaus Ambos-Spies, Hans-Christian Neis, and Sebastiaan A. Terwijn. Genericity and mea- sure for exponential time. volume 168, pages 3–19. 1996. 19th International Symposium on Mathematical Foundations of Computer Science (Koˇ sice, 1994)

    work page 1996

  2. [2]

    Cambridge University Press, Cambridge, 2009

    Sanjeev Arora and Boaz Barak.Computational complexity. Cambridge University Press, Cambridge, 2009. A modern approach

    work page 2009

  3. [3]

    Optimal redundancy in computations from random oracles.J

    George Barmpalias and Andrew Lewis-Pye. Optimal redundancy in computations from random oracles.J. Comput. System Sci., 92:1–8, 2018. 18

    work page 2018

  4. [4]

    Book, Jack H

    Ronald V. Book, Jack H. Lutz, and Klaus W. Wagner. An observation on probability versus randomness with applications to complexity classes.Math. Systems Theory, 27(3):201–209, 1994

    work page 1994

  5. [5]

    Hitchcock, and N

    Chris Bourke, John M. Hitchcock, and N. V. Vinodchandran. Entropy rates and finite-state dimension.Theoret. Comput. Sci., 349(3):392–406, 2005

    work page 2005

  6. [6]

    Dai, James I

    Jack J. Dai, James I. Lathrop, Jack H. Lutz, and Elvira Mayordomo. Finite-state dimension. InAutomata, languages and programming, volume 2076 ofLecture Notes in Comput. Sci., pages 1028–1039. Springer, Berlin, 2001

    work page 2076

  7. [7]

    Dimension extractors and optimal decompression.Theory Comput

    David Doty. Dimension extractors and optimal decompression.Theory Comput. Syst., 43(3- 4):425–463, 2008

    work page 2008

  8. [8]

    Downey and Denis R

    Rodney G. Downey and Denis R. Hirschfeldt.Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010

    work page 2010

  9. [9]

    Every sequence is reducible to a random one.Inform

    P´ eter G´ acs. Every sequence is reducible to a random one.Inform. and Control, 70(2-3):186– 192, 1986

    work page 1986

  10. [10]

    Hitchcock and N.V

    John M. Hitchcock and N.V. Vinodchandran. Dimension, entropy rates, and compression. Journal of Computer and System Sciences, 72(4):760–782, 2006

    work page 2006

  11. [11]

    Juedes and Jack H

    David W. Juedes and Jack H. Lutz. Weak completeness in e and e2.Theoretical Computer Science, 143(1):149–158, 1995

    work page 1995

  12. [12]

    Measure, Π0 1-classes and complete extensions of PA

    Anton´ ın Kuˇ cera. Measure, Π0 1-classes and complete extensions of PA. InRecursion theory week (Oberwolfach, 1984), volume 1141 ofLecture Notes in Math., pages 245–259. Springer, Berlin, 1985

    work page 1984

  13. [13]

    Texts in Computer Science

    Ming Li and Paul Vit´ anyi.An introduction to Kolmogorov complexity and its applications. Texts in Computer Science. Springer, New York, third edition, 2008

    work page 2008

  14. [14]

    Jack H. Lutz. Dimension in complexity classes.SIAM J. Comput., 32(5):1236–1259, 2003

    work page 2003

  15. [15]

    A Kolmogorov complexity characterization of constructive Hausdorff di- mension.Inform

    Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff di- mension.Inform. Process. Lett., 84(1):1–3, 2002

    work page 2002

  16. [16]

    On the construction of effectively random sets.J

    Wolfgang Merkle and Nenad Mihailovi´ c. On the construction of effectively random sets.J. Symbolic Logic, 69(3):862–878, 2004

    work page 2004

  17. [17]

    Real numbers equally compressible in every base

    Satyadev Nandakumar and Subin Pulari. Real numbers equally compressible in every base. ACM Trans. Comput. Theory, 17(3):Art. 16, 28, 2025

    work page 2025

  18. [18]

    One-way functions and polynomial time dimension.Electron

    Satyadev Nandakumar, Subin Pulari, Akhil S, and Suronjona Sarma. One-way functions and polynomial time dimension.Electron. Colloquium Comput. Complex., TR25-028, 2025

    work page 2025

  19. [19]

    OUP Oxford, 2009

    Andr´ e Nies.Computability and randomness, volume 51. OUP Oxford, 2009

    work page 2009

  20. [20]

    Wolfgang M. Schmidt. ¨ uber die Normalit¨ at von Zahlen zu verschiedenen Basen.Acta Arith., 7:299–309, 1961/62

    work page 1961

  21. [21]

    C. P. Schnorr and H. Stimm. Endliche automaten und zufallsfolgen.Acta Informatica, 1:345– 359, 1972. 19

    work page 1972

  22. [22]

    A complexity theoretic approach to randomness

    Michael Sipser. A complexity theoretic approach to randomness. InProceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 330–335, New York, NY, USA, 1983. Association for Computing Machinery

    work page 1983

  23. [23]

    Donald M. Stull. Resource bounded randomness and its applications. InAlgorithmic randomness—progress and prospects, volume 50 ofLect. Notes Log., pages 301–348. Cambridge Univ. Press, Cambridge, 2020. 20

    work page 2020