<p>There are several questions that you pose.  Let's address each one in turn:</p>
<ol start="0">
<li><p>What justifies the log in Kt complexity?
I think that the best answer is that Levin showed that, if you want to find satisfying assignments to a formula <span class="math-container">$\phi$</span> with <span class="math-container">$n$</span> variables, then an essentially optimal approach is to search through all <span class="math-container">$n$</span>-bit strings <span class="math-container">$x$</span> in order of increasing <span class="math-container">$Kt(x|\phi)$</span>.
.</p>
</li>
<li><p>Are there any special reasons why we only study Kt complexity and not <span class="math-container">$K^ft$</span>?
I myself have studied KT, which is <span class="math-container">$K^ft$</span> where <span class="math-container">$f=n$</span>.  The reason that I am interested in KT is that KT(x) is related to the circuit size required to compute the function with truth table <span class="math-container">$x$</span>.  If you find something interesting to say about <span class="math-container">$K^ft$</span> for other functions <span class="math-container">$f$</span>, that will provide good motivation for studying it.</p>
</li>
<li><p>Would it be interesting to show <span class="math-container">$K^{g\log}t\not\in P$</span> for some <span class="math-container">$g =\omega(1)$</span>?  Yes!  This would be very interesting.  For instance, if <span class="math-container">$g(n)=n/\log n$</span>, then <span class="math-container">$K^{g\log}t$</span> is KT (which is computable in <span class="math-container">$P^{NP}$</span>, and this would show P<span class="math-container">$\neq$</span> NP.  The consequences would not be nearly so dramatic for smaller functions <span class="math-container">$g$</span>, but it would still be very interesting.  Really, it seems like it should be obvious that Kt is not computable in polynomial time, since Kt is hard for EXP (under P/poly reductions) ... but of course we are currently unable to prove this.  Showing <span class="math-container">$K^{g\log}t\not\in P$</span> for some <span class="math-container">$g =\omega(1)$</span> seems like it would be even harder to prove, although this implication doesn't seem obvious to me right now.</p>
</li>
</ol>

CC BY-SA 4.0
2024-10-22T23:33:14.397Z
2024-10-22T23:33:14.397Z
Eric Allender
<p>Recall <span class="math-container">$Kt$</span> complexity and its lesser known brother <span class="math-container">$KT$</span> complexity. Call <span class="math-container">$x\in \{0;1\}^\ast$</span> a string we have the following definitions :</p>
<p><span class="math-container">$Kt(x) = \min \{ |p| + log(t) \quad ; \text{ program p outputs $x$ in $t$ steps} \}$</span></p>
<p><span class="math-container">$KT(x) = \min \{ |p| + t \quad ; \text{ program p outputs $x$ in $t$ steps} \}$</span></p>
<p>Those are the only kinds of temporal Kolmogorov complexity I've ever come across in  the literature, I'm under the impression the temporal bounds are kind of arbitrary therefore I introduce the following notion <span class="math-container">$K^ft$</span> where <span class="math-container">$f$</span> is a function :</p>
<p><span class="math-container">$K^ft(x) = \min \{ |p| + f(t) \quad ; \text{ program p outputs $x$ in $t$ steps} \}$</span></p>
<p>Recall the problem <span class="math-container">$MKtP$</span> (Minimum Kt problem) which where given <span class="math-container">$x$</span> you have to output <span class="math-container">$Kt(x)$</span>. Some smart people care to know if <span class="math-container">$MKtP \in P$</span> (There's apparently a relativizing barrier against that but not much else is known) . My questions are the following :</p>
<ol>
<li><p>Are there any special reasons why we only study <span class="math-container">$Kt$</span> complexity and not <span class="math-container">$K^ft$</span></p>
</li>
<li><p>Let's say hypothetically I could show <span class="math-container">$K^{g\log}t \not \in P$</span> for any <span class="math-container">$g=\omega(1)$</span>, would you care ? (in the sense is it trivial). Note that <span class="math-container">$K^{g\log}t$</span> is almost the usual <span class="math-container">$Kt$</span> complexity hence why anyone would care.</p>
</li>
</ol>

CC BY-SA 4.0
2024-10-22T14:50:52.557Z
FYI there is also time-bounded Kolmogorov complexity: K^t(x)=min{|p| : p outputs x in at most t(|x|) steps}. (And more generally resource-bounded, e.g. people have also looked at space-bounded.)
Joshua Grochow
CC BY-SA 4.0
2024-10-22T15:23:22.207Z
I edited the post, yes i am familiar with $K^t$
ULechine
<cc.complexity-theory><kolmogorov-complexity>
What justifies the $log$ in $Kt$ complexity ? (Variants of $Kt$ complexity with other bounds)
ULechine
# What justifies the $log$ in $Kt$ complexity ? (Variants of $Kt$ complexity with other bounds)

(Asked by: username_0 on 2024-10-22)

Recall $Kt$ complexity and its lesser known brother $KT$ complexity. Call $x\in \{0;1\}^\ast$ a string we have the following definitions :

$Kt(x) = \min \{ |p| + log(t) \quad ; \text{ program p outputs $x$ in $t$ steps} \}$

$KT(x) = \min \{ |p| + t \quad ; \text{ program p outputs $x$ in $t$ steps} \}$

Those are the only kinds of temporal Kolmogorov complexity I've ever come across in the literature, I'm under the impression the temporal bounds are kind of arbitrary therefore I introduce the following notion $K^ft$ where $f$ is a function :

$K^ft(x) = \min \{ |p| + f(t) \quad ; \text{ program p outputs $x$ in $t$ steps} \}$

Recall the problem $MKtP$ (Minimum Kt problem) which where given $x$ you have to output $Kt(x)$. Some smart people care to know if $MKtP \in P$ (There's apparently a relativizing barrier against that but not much else is known) . My questions are the following :

1. Are there any special reasons why we only study $Kt$ complexity and not $K^ft$
2. Let's say hypothetically I could show $K^{g\log}t \not \in P$ for any $g=\omega(1)$, would you care ? (in the sense is it trivial). Note that $K^{g\log}t$ is almost the usual $Kt$ complexity hence why anyone would care.

**Tags:** cc.complexity-theory, kolmogorov-complexity

> **Comments:**
> **username_1**: FYI there is also time-bounded Kolmogorov complexity: K^t(x)=min{|p| : p outputs x in at most t(|x|) steps}. (And more generally resource-bounded, e.g. people have also looked at space-bounded.)  
> **username_0**: I edited the post, yes i am familiar with $K^t$  

---

## 1 answers

### Answer by username_2 on 2024-10-22. Score: 4 | Accepted answer

There are several questions that you pose. Let's address each one in turn:

0. What justifies the log in Kt complexity?
   I think that the best answer is that Levin showed that, if you want to find satisfying assignments to a formula $\phi$ with $n$ variables, then an essentially optimal approach is to search through all $n$-bit strings $x$ in order of increasing $Kt(x|\phi)$.
   .
1. Are there any special reasons why we only study Kt complexity and not $K^ft$?
   I myself have studied KT, which is $K^ft$ where $f=n$. The reason that I am interested in KT is that KT(x) is related to the circuit size required to compute the function with truth table $x$. If you find something interesting to say about $K^ft$ for other functions $f$, that will provide good motivation for studying it.
2. Would it be interesting to show $K^{g\log}t\not\in P$ for some $g =\omega(1)$? Yes! This would be very interesting. For instance, if $g(n)=n/\log n$, then $K^{g\log}t$ is KT (which is computable in $P^{NP}$, and this would show P$\neq$ NP. The consequences would not be nearly so dramatic for smaller functions $g$, but it would still be very interesting. Really, it seems like it should be obvious that Kt is not computable in polynomial time, since Kt is hard for EXP (under P/poly reductions) ... but of course we are currently unable to prove this. Showing $K^{g\log}t\not\in P$ for some $g =\omega(1)$ seems like it would be even harder to prove, although this implication doesn't seem obvious to me right now.


---

