A. Milovanov

collaborators

2 papers

cs.CC2026

Limit on the computational power of $C$ -random strings

Alexey Milovanov

We construct a universal decompressor $U$ for plain Kolmogorov complexity $C_{U}$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with…

cs.CC2025

On the computational power of $C$ -random strings

Alexey Milovanov

Denote by $H$ the Halting problem. Let $R_{U} := {x ∣ C_{U} (x) \geq ∣ x ∣}$ , where $C_{U} (x)$ is the plain Kolmogorov complexity of $x$ under a universal decompressor $U$ . We prove that…

Limit on the computational power of C-random strings

On the computational power of C-random strings

Limit on the computational power of $C$ -random strings

On the computational power of $C$ -random strings