<blockquote>
<p>Let <span class="math-container">$f$</span> be an inverting problem. If there is an algorithm A that invert <span class="math-container">$f$</span> in time <span class="math-container">$t(n)$</span>, then the SIMPLE algorithm below invert <span class="math-container">$f$</span> in time <span class="math-container">$c.t(n)$</span> where <span class="math-container">$c$</span> is a constant depending only on <span class="math-container">$A$</span></p>
</blockquote>
<p>What does “<span class="math-container">$f$</span> is an inverting problem” mean? We can imagine <span class="math-container">$f^{-1}$</span> to be any function version of any problem in class <span class="math-container">$NP$</span>, to be exact, we are looking for some <em>witness</em> for the positive instances. for example <span class="math-container">$f^{-1}$</span> could be <span class="math-container">$FSAT$</span> (<em>function version of <span class="math-container">$SAT \in NP$</span>)</em>, in this case , if <span class="math-container">$\langle \phi \rangle \in SAT$</span> then <span class="math-container">$f^{-1}(\langle \phi \rangle)$</span> is a satisfying assignment. We can simplify that: <span class="math-container">$f$</span> is boolean formula and we are looking for <span class="math-container">$y$</span> <em>(a satisfying assignment)</em> such that <span class="math-container">$f(y)=True$</span>. Here we consider time complexity only for positive instances. Hence the input is an instance of a <span class="math-container">$NP$</span> problem. In the case of <span class="math-container">$FSAT$</span>, input is a description of a formula <span class="math-container">$\phi$</span>. Therefore <span class="math-container">$n=| \langle \phi \rangle |$</span>.</p>
<p>There is a simple variant of Levin universal search algorithm <em>(this variant is called SIMPLE)</em>, which runs all TM in a dovetailing style such that <span class="math-container">$M_i$</span> starts at <span class="math-container">$2^{i-1}$</span> and every consecutive step of <span class="math-container">$M_i$</span> has distance of <span class="math-container">$2^i$</span>. According to the sequence of indices: 1213121412131215121312141213121612…
If <span class="math-container">$M_k$</span> compute <span class="math-container">$f$</span> efficiently and we can check the correctness of the answer in linear time, then <span class="math-container">$M_k$</span> starts at <span class="math-container">$2^{k-1}$</span> and if its runtime is <span class="math-container">$t(n)$</span> then total runtime until <span class="math-container">$M_k$</span> finishes its job is <span class="math-container">$2^{k-1} + 2^k.t(n)$</span> without considering outputs that generated by TMs so far.</p>
<p>I think there is at least <span class="math-container">$\log t(n)$</span> TMs that maybe produce some wrong outputs that should be verified in linear time.</p>
<p>Where does this variant of Levin search come from? Originally i guess <em>Vitányi and Li</em> first mentioned this variant in their book <em>Kolmogrov Complexity … (1997)</em>. But this variant is also has been mentioned in <a href="http://hutter1.net/ai/pfastprg.pdf" rel="nofollow noreferrer"> Marcus hutter review paper</a> and Mark Gritter blog post about Levin search. In the main theorem by levin, i guess theorem stand on some assumption about simulating TMs <em>(fixed <span class="math-container">$k$</span>-tapes for instance)</em> and also if i’m not wrong, the simulator is a <em>Kolmogorov-Uspenski machine.</em> so i personally guess (and maybe i am wrong about it) that the simmulation overhead is somehow removed from the theorem by some extra assumptions.</p>
<p>So my first question is, i think there is <span class="math-container">$n \log t(n)$</span> more steps for checking bad outputs. So haven’t we another asumption in this theorem that say <span class="math-container">$t(n) &gt; n \log t(n)$</span> or am i wrong in calcuation of time ?</p>
<p>My second question is, where simmulation overhead considered ?</p>

CC BY-SA 4.0
2022-06-22T14:24:29.340Z
Another assumption in *what* theorem? You didn’t formulate any theorem.
Emil Jeřábek
CC BY-SA 4.0
2022-06-22T14:35:43.087Z
@EmilJeřábek Sorry for that. I did it now. (It is related to levin search and the fact that if P=NP , then we can construct an algorithm for NP problems which asymptoticly are efficient but maybe the constant factor being very large.)
Omid Yaghoubi
CC BY-SA 4.0
2022-06-23T06:15:47.147Z
It still does not say what $f$ is. But assuming from the context that you take it computable  in linear time, then verification of the correctness of the output $x_i$ of $M_i$ which finishes before $M_k$ does not take time $O(n)$, but time $O(|x_i|)$. Since $\sum_i|x_i|$ is at most the number of simulation steps taken by all those $M_i$ before $M_k$ finishes, it is $\le2^{k-1}+2^kt(n)$, hence the total time is still $O(2^kt(n))$ without any $n\log t(n)$ overhead.
Emil Jeřábek
CC BY-SA 4.0
2022-06-23T12:18:52.940Z
@EmilJeřábek Thanks !
Omid Yaghoubi
CC BY-SA 4.0
2022-06-24T10:47:16.267Z
@EmilJeřábek If $f=SAT$ then the input is a description of formula $\phi$ , so if $M_i$ output $x_i$ which $x_i$ is an assignment, shouldn’t we spend at least $O(|\langle \phi \rangle|)$ to evaluate $\phi[x_i]$ ?
Omid Yaghoubi
CC BY-SA 4.0
2022-06-24T12:00:40.397Z
Perhaps. The thing is, as I already mentioned, the question is too incomplete to answer. What does “$f$ is an inverting problem” mean, what exactly is referred to as $n$ in the statement, etc. And where does this variant of Levin search come from, actually?
Emil Jeřábek
CC BY-SA 4.0
2022-06-24T12:06:50.480Z
But I think that your biggest worry is the last question, actually. The way this is set up, the simulation is going to be very inefficient, as you are switching from one $M_i$ to another at each step: I can’t imagine how to implement that without constantly rewinding the tape, which gives a quadratic run time overhead. If you need the simulation to be efficient, you have to simulate each $M_i$ for longer time stretches to amortize the “context switching” costs.
Emil Jeřábek
CC BY-SA 4.0
2022-06-24T13:27:05.567Z
@EmilJeřábek I tried to describe all the unclearity that you mentioned in edited question. If there is still something that i should add to the question please tell me to do that.
Omid Yaghoubi
CC BY-SA 4.0
2022-06-24T13:58:10.323Z
@EmilJeřábek Sorry , because i often confused with $f$ with $f^{-1}$ , so i have some mistakes. So i edited my question again and i hope i did not make same mistake again.
Omid Yaghoubi
<complexity-theory><time-complexity><p-vs-np>
Number of outputs produced by levin search variant (SIMPLE)
Omid Yaghoubi
# Number of outputs produced by levin search variant (SIMPLE)

(Asked by: username_0 on 2022-06-17)

> Let $f$ be an inverting problem. If there is an algorithm A that invert $f$ in time $t(n)$, then the SIMPLE algorithm below invert $f$ in time $c.t(n)$ where $c$ is a constant depending only on $A$

What does “$f$ is an inverting problem” mean? We can imagine $f^{-1}$ to be any function version of any problem in class $NP$, to be exact, we are looking for some *witness* for the positive instances. for example $f^{-1}$ could be $FSAT$ (*function version of $SAT \in NP$)*, in this case , if $\langle \phi \rangle \in SAT$ then $f^{-1}(\langle \phi \rangle)$ is a satisfying assignment. We can simplify that: $f$ is boolean formula and we are looking for $y$ *(a satisfying assignment)* such that $f(y)=True$. Here we consider time complexity only for positive instances. Hence the input is an instance of a $NP$ problem. In the case of $FSAT$, input is a description of a formula $\phi$. Therefore $n=| \langle \phi \rangle |$.

There is a simple variant of Levin universal search algorithm *(this variant is called SIMPLE)*, which runs all TM in a dovetailing style such that $M\_i$ starts at $2^{i-1}$ and every consecutive step of $M\_i$ has distance of $2^i$. According to the sequence of indices: 1213121412131215121312141213121612…
If $M\_k$ compute $f$ efficiently and we can check the correctness of the answer in linear time, then $M\_k$ starts at $2^{k-1}$ and if its runtime is $t(n)$ then total runtime until $M\_k$ finishes its job is $2^{k-1} + 2^k.t(n)$ without considering outputs that generated by TMs so far.

I think there is at least $\log t(n)$ TMs that maybe produce some wrong outputs that should be verified in linear time.

Where does this variant of Levin search come from? Originally i guess *Vitányi and Li* first mentioned this variant in their book *Kolmogrov Complexity … (1997)*. But this variant is also has been mentioned in  [Marcus hutter review paper](http://hutter1.net/ai/pfastprg.pdf) and Mark Gritter blog post about Levin search. In the main theorem by levin, i guess theorem stand on some assumption about simulating TMs *(fixed $k$-tapes for instance)* and also if i’m not wrong, the simulator is a *Kolmogorov-Uspenski machine.* so i personally guess (and maybe i am wrong about it) that the simmulation overhead is somehow removed from the theorem by some extra assumptions.

So my first question is, i think there is $n \log t(n)$ more steps for checking bad outputs. So haven’t we another asumption in this theorem that say $t(n) > n \log t(n)$ or am i wrong in calcuation of time ?

My second question is, where simmulation overhead considered ?

**Tags:** complexity-theory, time-complexity, p-vs-np
> **Comments:**
> **username_1**: Another assumption in *what* theorem? You didn’t formulate any theorem.  
> **username_0**: @EmilJeřábek Sorry for that. I did it now. (It is related to levin search and the fact that if P=NP , then we can construct an algorithm for NP problems which asymptoticly are efficient but maybe the constant factor being very large.)  
> **username_1**: It still does not say what $f$ is. But assuming from the context that you take it computable  in linear time, then verification of the correctness of the output $x_i$ of $M_i$ which finishes before $M_k$ does not take time $O(n)$, but time $O(|x_i|)$. Since $\sum_i|x_i|$ is at most the number of simulation steps taken by all those $M_i$ before $M_k$ finishes, it is $\le2^{k-1}+2^kt(n)$, hence the total time is still $O(2^kt(n))$ without any $n\log t(n)$ overhead.  
> **username_0**: @EmilJeřábek Thanks !  
> **username_0**: @EmilJeřábek If $f=SAT$ then the input is a description of formula $\phi$ , so if $M_i$ output $x_i$ which $x_i$ is an assignment, shouldn’t we spend at least $O(|\langle \phi \rangle|)$ to evaluate $\phi[x_i]$ ?  
> **username_1**: Perhaps. The thing is, as I already mentioned, the question is too incomplete to answer. What does “$f$ is an inverting problem” mean, what exactly is referred to as $n$ in the statement, etc. And where does this variant of Levin search come from, actually?  
> **username_1**: But I think that your biggest worry is the last question, actually. The way this is set up, the simulation is going to be very inefficient, as you are switching from one $M_i$ to another at each step: I can’t imagine how to implement that without constantly rewinding the tape, which gives a quadratic run time overhead. If you need the simulation to be efficient, you have to simulate each $M_i$ for longer time stretches to amortize the “context switching” costs.  
> **username_0**: @EmilJeřábek I tried to describe all the unclearity that you mentioned in edited question. If there is still something that i should add to the question please tell me to do that.  
> **username_0**: @EmilJeřábek Sorry , because i often confused with $f$ with $f^{-1}$ , so i have some mistakes. So i edited my question again and i hope i did not make same mistake again.  

---

## 0 answers

