Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$. Normally in the analysis of algorithms or computational complexity theory, we have some sets $$I(n) = \{w \in S : |w| = n\}$$ of all inputs of length $n$, and a function $T(w)$ that gives the running time of some solution algorithm $A$ on input $w$. The worst-case running time sequence for $A$ is then $$ f_n = \max_{w \in I(n)} T(w). $$

Let us now define the sets $$ I^K(n) = \{w \in S : K(w) = n \}$$ of all inputs with Kolmogorov complexity $n$, and let us define the sequence $$ f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w). $$ Here $f^K$ is the average running time sequence for $A$, except where the "size" of inputs is their Kolmogorov complexity, not their length.

Are there algorithms for which $f_n$ is asymptotically significantly different from $f^K_n$? If so, are there problems whose time complexity changes when using this different way of analyzing algorithms?

  • 4
    $\begingroup$ Great question! One that I've often wondered about - I hope it gets some good answers. (I added the tag parameterized-complexity b/c you can view this as the question of the parameterized complexity of e.g. SAT, where the parameter is the Kolmogorov complexity.) $\endgroup$ Commented Feb 27, 2014 at 22:06
  • 3
    $\begingroup$ Random strings, aka most strings, have Kolmogorov complexity near their original length. For the vast majority of inputs $f_{n} = f_{n}^{K}$ You might get a more interesting result if you asked about computational depth instead of Kolmogorov complexity. google.com/… $\endgroup$ Commented Feb 27, 2014 at 22:40
  • 2
    $\begingroup$ By mixing in some instances of PARITY into a hard language to form $S$ (e.g. by prefixing each instance with a bit toggle that describes which language the instance is from), then $f^K_n$ will be smaller than $f_n$. Just how small depends on the relative density. $\endgroup$ Commented Feb 28, 2014 at 0:06
  • 1
    $\begingroup$ One place is in Vadhan's lecture notes here (Feb 19th): people.seas.harvard.edu/~salil/cs221/spring10/lectures.html $\endgroup$
    – usul
    Commented Feb 28, 2014 at 5:24
  • 1
    $\begingroup$ @AndrásSalamon, yeah, I hope I am not being too sloppy, but I think $n \mapsto \max_{w: K(w)=n} |w|$ should essentially be the busy-beaver function. $\endgroup$
    – usul
    Commented Feb 28, 2014 at 21:19

3 Answers 3


Consider the parity function (or any other function that depends on all/most bits of the input). For the parity function, $T(w) = \Theta(|w|)$. So $$f_n = \Theta(n).$$ On the other hand, $$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$

Note that $K(2^{2^n}) = O(n)$. Thus $$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$$ and $f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$. Similarly, $K(2^{\dots^{2^{2^n}}}) = O(n)$; thus $f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$ “grows very rapidly”. Moreover, it's not hard to see that there is no computable upper bound for $f_n^K$.


Given the interest in this question, I thought it might be helpful to point out more explicitly the reason we should not be at all surprised by the answer and try to give some direction for refinements of the question. This collects and expands on some comments. I apologize if this is "obvious"!

Consider the set of strings of Kolmogorov complexity $n$: $$J^K(n) = \{w : K(w) = n\}. $$ There are at most $2^n$ such strings, as there are $2^n$ descriptions of length $n$. But notice that this set is undecidable for general $n$ (otherwise, we could compute $K(w)$ just by iterating from $n=1$ to $|w|$ and checking membership in $J^K(n)$). Furthermore, the function $$g^K(n) = \max_{w \in J^K(n)} |w|$$ grows uncomputably fast. It is a variant of the busy-beaver function: what is the longest output by a Turing Machine of description length $n$? If this grew slower than some computable function, we could decide the halting problem: Given a TM $M$, construct $M'$ that simulates $M$ and prints a $1$ at every step. If the description length of $M'$ is $n$, then either: $M$ halts in at most $g^K(n)$ steps; or $M$ does not halt.

Now, to Andrew's question, we have that $I^K(n) = S \cap J^K(n)$, where $S$ is the original language. So the only way to avoid $I^K(n)$ containing inputs very large in $n$ would be if $S$ contains only very uncompressible strings. (Note that, otherwise, we can completely ignore the distinction between worst-case and average-case analysis here, because we average over at most $2^n$ strings but the size of the largest string is growing faster than any computable function of $n$.)

I feel that it is likely impossible to construct any nontrivial (i.e. infinite) $S$ that contains only uncompressible strings, yet is decidable. But I don't know. However, hopefully this gives intuition as to why we should not hope for most languages to have $f^K_n$ growing slower than a computable function.

To step back slightly, the question is to compare performance on inputs of length $n$ to performance on inputs that can be compressed to length $n$. But we have notions of compression that are much more tractable (and less powerful) than Kolmogorov Complexity. A simple way is to give a circuit of size $n$, which on input the binary number $b$ produces the $b$th bit of $w$. Note that here the blowup in input size is at most exponential (a circuit of size $n$ has at most $2^n$ possible inputs).

So we can rephrase the question by letting $$ I^C(n) = \{ w \in S : \text{the smallest circuit implicitly specifying $w$ has size $n$}\}. $$ And define $f^C_n$ analogously. The reason for hope here is that most strings require a circuit almost as large as the string itself, and no strings are more than exponentially larger than the circuit required. Perhaps in this case we could find languages where $f_n$ and $f^C_n$ are similar asymptotically.

A pretty closely related question is the complexity of implicit languages like $$ \mathsf{IMPLICIT\_SAT} = \{ \text{circuits $C$}: \text{$C$ implicitly specifies $w$}, w \in \mathsf{SAT}\}. $$ IMPLICIT_SAT is NEXP-complete, and usually the implicit version of NP-complete problems are NEXP-complete. Deciding IMPLICIT_SAT is at least as easy as just using the circuit to write out all of $w$, then running an algorithm for SAT on $w$. So if $f^C_n = \Theta(f_n)$ for SAT, then this seems close to giving evidence that IMPLICIT_SAT in the average-case is almost as quickly decidable as SAT is in the worst-case. But I don't know how one would directly compare your notion to implicit languages because the notion of "smallest circuit for $w$" does not come into play for implicit languages.

Hope this is helpful/interesting!

I'm not sure of a textbook that mentions implicit problems, but here are some lecture notes: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

  • $\begingroup$ $\left|J^K(n)\right| = 2^n$? But not every description is minimal. $\endgroup$
    – Andrew
    Commented Mar 4, 2014 at 3:20
  • 1
    $\begingroup$ @AndrewMacFie, right, should be "at most". Will fix. $\endgroup$
    – usul
    Commented Mar 4, 2014 at 14:50
  • $\begingroup$ Thanks for adding this answer :) It sounds like for any algorithm for 3-SAT, $f^K_n$ is going to grow fast. $\endgroup$
    – Andrew
    Commented Mar 18, 2014 at 22:31

An easy case seems to be where the language $S$ contains only padded instances. When $S$ is obtained from a language $L$ by padding each instance of size $n$ with $2^n-n$ symbols, $f^K_{n}$ can be in the region of $2^{f_n}$.

  • $\begingroup$ Note that Yury's answer subsumes this one, and also makes precise the "can be in the region of". $\endgroup$ Commented Feb 27, 2014 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.