Lower Bound on the difference between uniform and prefix-free complexity

Question

The uniform Kolmogorov complexity (also known as decision complexity) of a string $\sigma$ is defined as follows: let $\phi: 2^{<\omega} \times \mathbb{N} \rightarrow {0,1}$ be a partial computable function. A string $\tau$ is called a description of $\sigma$ relative to $\phi$ if $\phi(\tau,i) = \sigma_i$ for $i = 1 \cdots l(\sigma)$, where $l(\sigma)$ denotes the length of $\sigma$. The uniform complexity $Ku(\sigma)$ of $\sigma$ is defined as the length of the shortest description of $\sigma$ relative to a universal machine.

It is clear that $Ku(\sigma) \le K(\sigma) + O(1)$ when $K$ is the prefix-free complexity. But how good is this inequality? More specifically I look for infinitely many strings $\tau_i$ with $Ku(\tau_i) \ge K(\sigma) - O(1)$. I can find such strings if the uniform complexity is replaced by the a priori complexity (sometimes denoted by $KM$), but I can't find these strings for $Ku$ (which would be a stronger statement).

The existence of such strings is equivalent to the existence of strings $\tau_i$ with $\sum_i 2^{-Ku(\tau_i)} \le c$ for some constant $c$.

I think that these string have to be incomparable relative to the prefix ordering (take for example the strings $0^n1$), but I don't know how proof the claim.

Thanks and aurevoir

Answer 1

Lance Forthnow's example works to separate decision complexity and prefix-complexity: $Ku(0^n) \le O(1)$ for all $n$, and at the same time $K(0^n) > \log n$ for infinitely many $n$.

Note that $Ku(x) \le C(x) + O(1)$ where $C(x)$ denotes the plain complexity of $x$.

Decision complexity can also be lower than the logarithm of a priori probability. The argument is similar as the standard argument to separate plain and prefix complexity: we take advantage of the length of a program to encode an initial segment of a string. More formally, consider a long anough string $x$ such that for each $i < |x|$ we have $M(x_1...x_i) \le M(x_1...x_{i-1})/2$. Clearly we have $KM(x_1...x_i) \ge i$. Let $n \le |x|$ be a number whose binary representation is an initial segment of $x$. A uniform program of length $n - \log n + O(\log \log n)$ is obtained as follows: if $i \le \log n$ return the $i$-th bit of $n$ in binary, if $i \ge \log n$, return the corresponding bit in a literal representation of $x_{1 + \log n}...x_n$. For this program, we need to encrypt $\log n$ and $x_{1 + \log n}...x_n$. [The value $n$ can be recovered from $\log n$ and the length of the program.]