3 ms·
>uniform random strings’ K complexity is only _tightly concentrated around_ the strings’ length plus a machine-dependent constant What is the distribution of t
by l33t7332273 2y ago
>uniform random strings’ K complexity is only _tightly concentrated around_ the strings’ length plus a machine-dependent constant
What is the distribution of the complexity of a string? Is there some Chernof-like bound?