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?

  • $\begingroup$ 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}$. $\endgroup$
    – Thomas
    Sep 27 '16 at 19:23
  • $\begingroup$ @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 $\endgroup$ Sep 27 '16 at 19:31
  • $\begingroup$ 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. $\endgroup$ Sep 30 '16 at 13:56
  • $\begingroup$ @ChadBrewbaker you need uncomputable much memory to know busy beavers $\endgroup$ 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.