Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 Aug 30 '11 at 15:08

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.