Take the 2-minute tour ×
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.

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?

share|improve this question
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.) –  Joshua Grochow Feb 27 at 22:06
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/… –  Chad Brewbaker Feb 27 at 22:40
Thanks for the answers so far. It seems that $f_n^K$ can be much greater than $f_n$. Can $f_n^K$ be much less than $f_n$? –  Andrew MacFie Feb 27 at 23:03
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. –  András Salamon Feb 28 at 0:06
One place is in Vadhan's lecture notes here (Feb 19th): people.seas.harvard.edu/~salil/cs221/spring10/lectures.html –  usul Feb 28 at 5:24

3 Answers 3

up vote 15 down vote accepted

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

share|improve this answer

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

share|improve this answer
$\left|J^K(n)\right| = 2^n$? But not every description is minimal. –  Andrew MacFie Mar 4 at 3:20
@AndrewMacFie, right, should be "at most". Will fix. –  usul Mar 4 at 14:50
Thanks for adding this answer :) It sounds like for any algorithm for 3-SAT, $f^K_n$ is going to grow fast. –  Andrew MacFie Mar 18 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}$.

share|improve this answer
Note that Yury's answer subsumes this one, and also makes precise the "can be in the region of". –  András Salamon Feb 27 at 23:09

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.