# Difference between time-bounded and memory-bounded Kolmogorov complexity

Let $x$ be a finite string of length $n$.

Denote by $C^t(x)$ the Kolmogorov complexity of $x$ bounded by time $t$ (i.e. the length of a minimal program that outputs $x$ and running at most $t$ steps).

Denote by $C_m(x)$ the Kolmogorov complexity of $x$ bounded by memory $m$.

Can $C^{\mathsf{poly}(n)}(x)$ be much greater than $C_{\mathsf{poly}(n)}(x)$? It seems that the answer is "yes" but how to prove it under natural assumptions?

More accurately: let $(x_i)$ be a sequence of finite strings. Is it true that for every polynomial $p$ there exist a polynomial $q$ and a constant $c$ such that for every $x_i$ of length $n$ the following inequality holds: $$C^{q(n)}(x_i) < C_{p(n)}(x_i) + c\log n ?$$ Does it contradict to some natural assumptions of Computational complexity theory?

• My guess is that it should be easy to show that $C^{\text{poly}(|x|)}(x) \leq C_{\text{poly}(|x|)}(x)$ for all $x$ if and only if $\mathsf{P}=\mathsf{PSPACE}$. – Thomas supports Monica Sep 27 '16 at 19:23
• @Thomas I think it is true if we consider $C^{\mathsf{poly}(|x| + |y|)}(x | y)$ vs $C_{\mathsf{poly}(|x| + |y|)}(x | y)$ like at Theorem 7.6 here: lance.fortnow.com/papers/files/cd.pdf – Alexey Milovanov Sep 27 '16 at 19:31
• For random sequences t=m=length(x). Busy beavers seem to be an edge case. For known busy beavers how much memory do they use? Log(uncomputable)? It can't be constant. – Chad Brewbaker Sep 30 '16 at 13:56
• @ChadBrewbaker you need uncomputable much memory to know busy beavers – Alexey Milovanov Sep 30 '16 at 13:58

Assume that there exists a sparse set $L \in \mathbf{NP} -\mathbf{P}$, this is equivalent to $\mathbf{EXP}\not= \mathbf{NEXP}$.

Then we can construct such a sequence. Indeed, consider $L_n = \{l_1,\ldots, l_k\} = L \cap \{0,1\}^n$.

Denote by $s_i$ the lexicographically first certificate for $l_i$.

Define $x_n$ as the list of pairs: $x_n:= \{ (l_1, s_1), \ldots, (l_k,s_k)\}$.

Certainly, $C_{\mathsf{poly}(n)}(x_n) = O(\log n)$. Let us show that $C^{\mathsf{poly}(n)}(x_n) > c\log n$ for every $c$.

Indeed, otherwise there exists a polynomial-time algorithm calculating all strings of complexity at most $c\log n$ (including $x_n$). Hence we can verify that a string belongs to $L$ in polynomial time.

• Furthermore, that still works when "memory-bounded" is replaced with "time-bounded NP-oracle". ​ ​ – user6973 Oct 17 '16 at 1:24