Limit on the computational power of C \mathrm{C} -random strings

Alexey Milovanov · 2026

Read Limit on the computational power of C \mathrm{C} -random strings by Alexey Milovanov (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-16261.txt.

Introduction

Milovanov constructs a universal decompressor for plain Kolmogorov complexity such that the Halting Problem cannot be decided by any polynomial-time oracle machine given the set of random strings. The result resolves a problem posed by Eric Allender about the computational power of Kolmogorov-complexity-based oracles. The proof builds the decompressor so its random set defeats every polynomial-time oracle machine on the Halting Problem. It thus limits what random-string oracles can compute, even with full polynomial-time machinery.

Catalog record

CREATORAlexey Milovanov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97797
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Limit on the computational power of C \mathrm{C} -random strings Alexey Milovanov Abstract We construct a universal decompressor U U for plain Kolmogorov complexity C U \mathrm{C}_{U} such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings R C U = { x : C U ​ ( x ) ≥ | x | } R_{\mathrm{C}_{U}}=\{x:\mathrm{C}_{U}(x)\geq|x|\} . This result resolves a problem posed by Eric Allender in [ 1 ] regarding the computational power of Kolmogorov complexity-based oracles. 1 Introduction Informally the Kolmogorov complexity of a string x is defined as the minimal length of a program that outputs x on the empty input. This definition requires refinement; there are various types of complexity (plain, prefix, and others), but even once the type is fixed, there remains a dependency on the choice of the programming language or decompressor. We provide all the definitions needed for this paper in Section 3 ; we also refer the reader to [ 8 , 12 ] for formal definitions and the main properties of Kolmogorov complexity. Kolmogorov complexity provides a notion of an individual random string: a string x is considered random if its complexity is close to its length. Let R denote the set of all such random strings. A natural question is: how powerful is the oracle R ? For example, what languages belong to \mathrm{P}^{R} ? This and similar questions were investigated in [ 2 , 3 , 6 ] . In these papers, some lower bounds for \mathrm{P}^{R} , \mathrm{P}/\mathrm{poly}^{R} , and other complexity classes were established. These results are robust in the following sense: they hold for all reasonable definitions of R ; in particular, it does not matter what type of Kolmogorov complexity we consider. How are these non-trivial lower bounds for classes such as \mathrm{BPP}^{R} (which equals \mathrm{P}^{R} [ 3 ] ) obtained? The key observation is that access to R allows a machine to distinguish true randomness from pseudorandomness, effectively breaking any computable pseudorandom generator. Since this argument works for essentially any natural definition of the set of random strings R , it suggests that the computational power of \mathrm{P}^{R} should be invariant across standard definitions of R . However, proving this invariance—and in particular, establishing matching upper bounds —turns out to be exceptionally difficult. The situation for upper bounds is highly sensitive to the specific definition of complexity. The results in [ 4 , 5 , 9 ] establish limits on the computational power of R specifically for prefix complexity. For example, the results in [ 4 , 5 ] together with the lower bound obtained in [ 6 ] show that \text{EXP}^{\text{NP}}\subseteq\bigcap_{U}\mathrm{P}^{R_{\text{K}_{U}}}\subseteq\mathrm{EXPSPACE}. Here, the intersection is taken over all universal prefix-free decompressors U . While there is a significant gap between the lower and upper bounds for prefix complexity, it is at least known that the intersection does not contain any undecidable language. For plain complexity, even this basic limitation remained unknown. Prior to our work, it was an open question whether the Halting Problem could be decided by a polynomial-time machine with access to the plain complexity oracle. This paper provides a definitive step towards clarifying the situation for plain complexity. Let \mathrm{C}_{U}(x) denote the plain Kolmogorov complexity of a string x with respect to a universal decompressor U . Instead of working directly with the set of random strings, we consider the stronger cumulative complexity oracle: F_{\mathrm{C}_{U}}=\{\langle x,k\rangle\in\{0,1\}^{*}\times\mathbb{N}:\mathrm{C}_{U}(x)\leq k\}. Let H denote the Halting Problem: H:=\{x\mid\text{program }x\text{ halts on the empty input}\}. Our main result is the following theorem. Theorem 1.1 . There exists a universal decompressor U such that H\notin\mathrm{P}^{F_{\mathrm{C}_{U}}} . Corollary 1.2 . Let R_{\mathrm{C}_{U}}=\{x\in\{0,1\}^{*}:\mathrm{C}_{U}(x)\geq|x|\} be the set of random strings. Then H\notin\mathrm{P}^{R_{\mathrm{C}_{U}}} . Related works In [ 10 ] , it was shown that for some universal U the Halting Problem belongs to \mathrm{P}^{R_{\mathrm{C}_{U}}} . Together with our main result, this implies that the computational power of \mathrm{P}^{R_{\mathrm{C}_{U}}} significantly depends on the choice of the universal machine U . In [ 7 ] , Kummer showed that for each universal machine U , there is a time-bounded disjunctive truth-table reduction from H to R_{U} . That is, there is a computable function that takes an input x and produces a list of strings, with the property that x\in H if and only if at least one of the strings is in R_{U} . Therefore, the polynomial restriction in Theorem 1.1 is significant. Roadmap In Section 2 , we present a comprehensive technical overview of our framework, including the underlying combinatorial game and the formal statement of the Key Lemma. In Section 3 , we recall the definition of plain Kolmogorov complexity and its basic properties. Section 4 proves the main theorem. Section 5 contains the formal proof of the Key Lemma. Finally, omitted proofs of auxiliary statements are provided in the Appendix. 2 Framework of the Proof Our goal is to construct a universal machine U such that H\notin\mathrm{P}^{F_{\mathrm{C}_{U}}} . We first show that if the Halting Problem were solvable in polynomial time relative to F_{\mathrm{C}_{U}} , then a certain counting problem would also be solvable in polynomial time. The core of our paper is then to construct a specific U that forces any polynomial-time oracle machine to fail at this task. 2.1 From the Halting Problem to Counting Let U be an arbitrary universal decompressor. We define the following task relative to U . Definition 2.1 ( COUNT-SIMPLE ) . Given input 1^{m} , output the integer N_{m} representing the count of all strings with complexity at most m with respect to U : N_{m}=\left|\{x\in\{0,1\}^{*}:\mathrm{C}_{U}(x)\leq m\}\right|. Since any string x with \mathrm{C}_{U}(x)\leq m is generated by a program of length at most m , we have the natural bound 0\leq N_{m}<2^{m+1} . The connection between the Halting Problem and this counting task is captured by the following lemma. Lemma 2.2 (Implication of H\in\mathrm{P}^{F_{\mathrm{C}_{U}}} ) . If H\in\mathrm{P}^{F_{\mathrm{C}_{U}}} , then there is a polynomial-time machine M with oracle F_{\mathrm{C}_{U}} that on input 1^{m} outputs N_{m} (i.e., solves COUNT-SIMPLE ). Proof sketch. Consider the predicate Q(m,k) : “Do there exist at least k strings x with \mathrm{C}_{U}(x)\leq m ?” If H\in\mathrm{P}^{F_{\mathrm{C}_{U}}} , a polynomial-time machine can decide Q(m,k) . Using a standard binary search, the machine can pinpoint the exact value of N_{m} in O(m) queries. The formal proof is deferred to the Appendix. ∎ 2.2 The Architecture of the Universal Machine U We construct our universal machine U by combining a fixed optimal decompressor V with a constructed partial computable function G . This architecture also depends on a constant d\geq 1 . Both G and d will be formally determined in subsequent sections. Definition 2.3 (Universal Machine Structure) . Given a fixed optimal universal decompressor V , a partial computable function G , and a constant d\geq 1 , we define the machine U on input w\in\{0,1\}^{*} as follows: 1. Simulation Mode: If w=0^{d}p (a string of d zeros followed by p ), then U(w)=V(p) . 2. Diagonalization Mode: If w=1p , then U(w)=G(p) . This ensures that U is a universal decompressor, since \mathrm{C}_{U}(x)\leq\mathrm{C}_{V}(x)+d for all x . This bound holds regardless of how we define

Read the complete text