<p>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) &gt; \log n$ for infinitely many $n$.</p>

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

<p>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 &lt; |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.]</p>

CC BY-SA 3.0
2013-02-16T15:19:06.940Z
2013-02-16T15:19:06.940Z
Bruno Bauwens
<p>The uniform Kolmogorov complexity (also known as decision complexity) of a string $\sigma$ is defined as follows: let $\phi: 2^{&lt;\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. </p>

<p>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).</p>

<p>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$.</p>

<p>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.</p>

<p>Thanks and 
aurevoir</p>

CC BY-SA 3.0
2011-08-30T15:08:51.593Z
I'm not understanding this definition. Looks like $Ku(0^n)=O(1)$ for every $n$ with the $\tau$ such that $\phi(\tau,i)=0$ for all $i$.
Lance Fortnow
<cc.complexity-theory><kolmogorov-complexity>
Lower Bound on the difference between uniform and prefix-free complexity
aurevoirlesenfants
# Lower Bound on the difference between uniform and prefix-free complexity

(Asked by: username_0 on 2010-10-22)

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

**Tags:** cc.complexity-theory, kolmogorov-complexity

> **Comments:**
> **username_1**: I'm not understanding this definition. Looks like $Ku(0^n)=O(1)$ for every $n$ with the $\tau$ such that $\phi(\tau,i)=0$ for all $i$.  

---

## 1 answers

### Answer by username_2 on 2013-02-16. Score: 2

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.]


---

