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

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 access to the set of random strings $R_{C_{U}} = {x : C_{U} (x) \geq ∣ x ∣}$ . This result resolves a problem posed by Eric Allender regarding the computational power of Kolmogorov complexity-based oracles.

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

文献摘要

讨论

讲解博客

AI智能校验

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

文献摘要

讨论

讲解博客

AI智能校验

Limit on the computational power of CC-random strings

文献摘要

讨论

|讲解博客

|AI智能校验

Limit on the computational power of CC-random strings

文献摘要

讨论

|讲解博客

|AI智能校验

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

讲解博客

AI智能校验

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

讲解博客

AI智能校验