Using Kolmogorov complexity as input "size"

Question

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?

Answer 1

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 2

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

Answer 3

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