Difference between time-bounded and memory-bounded Kolmogorov complexity

Question

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?

Answer 1

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.