<p>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"!</p>

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

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

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

<p>To step back slightly, the question is to compare performance on inputs of length $n$ to performance on inputs that can be <em>compressed</em> 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).</p>

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

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

<p>Hope this is helpful/interesting!</p>

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

CC BY-SA 3.0
2014-03-04T03:20:34.990Z
$\left|J^K(n)\right| = 2^n$?  But not every description is minimal.
Andrew
CC BY-SA 3.0
2014-03-04T14:50:28.933Z
@AndrewMacFie, right, should be "at most". Will fix.
usul
CC BY-SA 3.0
2014-03-18T22:31:58.193Z
Thanks for adding this answer :) It sounds like for any algorithm for 3-SAT, $f^K_n$ is going to grow fast.
Andrew
CC BY-SA 3.0
2014-03-01T10:49:35.537Z
2014-03-04T14:51:40.890Z
2014-03-04T14:51:40.890Z
usul
<p>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}$.</p>

CC BY-SA 3.0
2014-02-27T23:09:58.273Z
Note that Yury's answer subsumes this one, and also makes precise the "can be in the region of".
András Salamon
CC BY-SA 3.0
2014-02-27T22:56:07.703Z
2014-02-27T22:56:07.703Z
András Salamon
<p>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).$$</p>

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

CC BY-SA 3.0
2014-02-27T22:49:20.687Z
2014-02-27T22:49:20.687Z
Yury
<p>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). $$ </p>

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

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

CC BY-SA 3.0
2014-02-27T22:06:18.117Z
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
CC BY-SA 3.0
2014-02-27T22:40:02.437Z
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. https://www.google.com/search?q=computational+depth&oq=computational+depth
Chad Brewbaker
CC BY-SA 3.0
2014-02-27T23:03:42.487Z
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
CC BY-SA 3.0
2014-02-28T00:06:03.053Z
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
CC BY-SA 3.0
2014-02-28T01:53:46.297Z
Andrew, are you familiar with implicit problems? Even if the input is specified by a circuit (much easier than being the output of some arbitrary TM) the language becomes much harder to decide in the worst case, which I think likely implies average case as well for many problems.
usul
CC BY-SA 3.0
2014-02-28T01:58:11.173Z
@AndrásSalamon, how so? As far as I can tell, if $T(w)$ is not bounded by a constant, then $f_n^K$ grows uncomputably fast because $|w|$ does. (Unless $T(w)$ were somehow constant on precisely the strings that are "fast-growing" outputs, but this would be undecidable even by looking at the whole string.)
usul
CC BY-SA 3.0
2014-02-28T04:25:49.380Z
@usul I'll have to look into implicit problems
Andrew
CC BY-SA 3.0
2014-02-28T05:24:47.277Z
One place is in Vadhan's lecture notes here (Feb 19th): http://people.seas.harvard.edu/~salil/cs221/spring10/lectures.html
usul
CC BY-SA 3.0
2014-02-28T10:41:52.837Z
@usul: One is comparing the average runtime of $A$ over each $I^K(n)$ with the maximum runtime over each $I(n)$.  As long as $I(n)$ and $I^K(n)$ are "not too different", the average will be smaller than the maximum.  Note that I was thinking of decidable problems and an algorithm $A$ that always terminates, so $T(w)$ is always finite; were you considering $T(w)$ being infinite for some inputs $w$?  Not sure what Andrew intended, might be worth clarifying.
András Salamon
CC BY-SA 3.0
2014-02-28T14:47:52.097Z
@AndrásSalamon, it seems to me that it is very difficult to ensure that $I(n)$ and $I^K(n)$ are not too different. Essentially, we wish to require that $I^K(n)$ contains no strings much longer than $n$ (say no longer than $g(n)$, where maybe $g(n) = 2^{2^n}$). But for instance the set $\{w : K(w) = n, |w| \leq g(n)\}$ is undecidable, so I think any language for which $I^K(n)$ contains only small strings is likely to be undecidable as well...?
usul
CC BY-SA 3.0
2014-02-28T16:09:04.397Z
@usul: Good point, mixing an easy and a hard language in some proportion may not help here.  Could you provide more detail about your idea of $f^K_n$ necessarily growing uncomputably fast?
András Salamon
CC BY-SA 3.0
2014-02-28T21:19:29.070Z
@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.
usul
<cc.complexity-theory><kolmogorov-complexity><parameterized-complexity><succinct><analysis-of-algorithms>
Using Kolmogorov complexity as input "size"
Andrew
# Using Kolmogorov complexity as input "size"

(Asked by: username_0 on 2014-02-27)

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?

**Tags:** cc.complexity-theory, kolmogorov-complexity, parameterized-complexity, succinct, analysis-of-algorithms

> **Comments:**
> **username_1**: 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.)  
> **username_2**: 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. https://www.google.com/search?q=computational+depth&oq=computational+depth  
> **username_0**: 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$?  
> **username_3**: 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.  
> **username_4**: username_0, are you familiar with implicit problems? Even if the input is specified by a circuit (much easier than being the output of some arbitrary TM) the language becomes much harder to decide in the worst case, which I think likely implies average case as well for many problems.  
> **username_4**: @AndrásSalamon, how so? As far as I can tell, if $T(w)$ is not bounded by a constant, then $f_n^K$ grows uncomputably fast because $|w|$ does. (Unless $T(w)$ were somehow constant on precisely the strings that are "fast-growing" outputs, but this would be undecidable even by looking at the whole string.)  
> **username_0**: @username_4 I'll have to look into implicit problems  
> **username_4**: One place is in Vadhan's lecture notes here (Feb 19th): http://people.seas.harvard.edu/~salil/cs221/spring10/lectures.html  
> **username_3**: @username_4: One is comparing the average runtime of $A$ over each $I^K(n)$ with the maximum runtime over each $I(n)$.  As long as $I(n)$ and $I^K(n)$ are "not too different", the average will be smaller than the maximum.  Note that I was thinking of decidable problems and an algorithm $A$ that always terminates, so $T(w)$ is always finite; were you considering $T(w)$ being infinite for some inputs $w$?  Not sure what username_0 intended, might be worth clarifying.  
> **username_4**: @AndrásSalamon, it seems to me that it is very difficult to ensure that $I(n)$ and $I^K(n)$ are not too different. Essentially, we wish to require that $I^K(n)$ contains no strings much longer than $n$ (say no longer than $g(n)$, where maybe $g(n) = 2^{2^n}$). But for instance the set $\{w : K(w) = n, |w| \leq g(n)\}$ is undecidable, so I think any language for which $I^K(n)$ contains only small strings is likely to be undecidable as well...?  
> **username_3**: @username_4: Good point, mixing an easy and a hard language in some proportion may not help here.  Could you provide more detail about your idea of $f^K_n$ necessarily growing uncomputably fast?  
> **username_4**: @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.  

---

## 3 answers

### Answer by username_5 on 2014-02-27. Score: 14 | Accepted answer

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


---

### Answer by username_4 on 2014-03-01. Score: 9

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 username_0'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>

> **Comments:**
> **username_0**: $\left|J^K(n)\right| = 2^n$?  But not every description is minimal.  
> **username_4**: @username_0MacFie, right, should be "at most". Will fix.  
> **username_0**: Thanks for adding this answer :) It sounds like for any algorithm for 3-SAT, $f^K_n$ is going to grow fast.  

---

### Answer by username_3 on 2014-02-27. Score: 4

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

> **Comments:**
> **username_3**: Note that username_5's answer subsumes this one, and also makes precise the "can be in the region of".  

---

