Some properties of antistochastic strings

Antistochastic strings are those strings that lack any reasonable statistical explanations. We establish the follow property of such strings: every absolutely non-stochastic string $x$ is "holographic" in the sense that it can be restored by a short program from any its part whose length equals the Kolmogorov complexity of $x$. Further we will show how it can be used for list decoding from erasing and for prove that symmetry of information fails for total conditional complexity.

No reviews yet.

No comments yet.