<p>Assume that there exists a sparse set $L \in \mathbf{NP} -\mathbf{P}$, this is <a href="http://www.sciencedirect.com/science/article/pii/S0019995885800048" rel="nofollow">equivalent</a> to $\mathbf{EXP}\not= \mathbf{NEXP}$.</p>

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

<p>Denote by $s_i$ the lexicographically first certificate for $l_i$. </p>

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

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

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

CC BY-SA 3.0
2016-10-15T22:28:25.393Z
2016-10-16T23:06:06.433Z
2016-10-16T23:06:06.433Z
Alexey Milovanov
<p>Let $x$ be a finite string of length $n$.</p>

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

<p>Denote by $C_m(x)$ the Kolmogorov complexity of $x$ bounded by memory $m$.</p>

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

<p>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) &lt;  C_{p(n)}(x_i) + c\log n ?$$
Does it contradict to some natural assumptions of Computational complexity theory?</p>

CC BY-SA 3.0
2016-09-27T19:23:44.150Z
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 Steinke
CC BY-SA 3.0
2016-09-27T19:31:41.670Z
@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: http://lance.fortnow.com/papers/files/cd.pdf
Alexey Milovanov
CC BY-SA 3.0
2016-09-30T13:56:09.537Z
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
CC BY-SA 3.0
2016-09-30T13:58:48.433Z
@ChadBrewbaker you need uncomputable much memory to know busy beavers
Alexey Milovanov
<cc.complexity-theory><kolmogorov-complexity>
Difference between time-bounded and memory-bounded Kolmogorov complexity
Alexey Milovanov
# Difference between time-bounded and memory-bounded Kolmogorov complexity

(Asked by: username_0 on 2016-09-27)

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?

**Tags:** cc.complexity-theory, kolmogorov-complexity
> **Comments:**
> **username_1**: 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}$.  
> **username_0**: @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: http://lance.fortnow.com/papers/files/cd.pdf  
> **username_2**: 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.  
> **username_0**: @ChadBrewbaker you need uncomputable much memory to know busy beavers  

---

## 1 answers

### Answer by username_0 on 2016-10-15. Score: 3

Assume that there exists a sparse set $L \in \mathbf{NP} -\mathbf{P}$, this is [equivalent](http://www.sciencedirect.com/science/article/pii/S0019995885800048) 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.


---

