# Number of outputs produced by levin search variant (SIMPLE)

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

• Another assumption in what theorem? You didn’t formulate any theorem. Jun 22 at 14:24
• @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.) Jun 22 at 14:35
• 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. Jun 23 at 6:15
• @EmilJeřábek Thanks ! Jun 23 at 12:18
• 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. Jun 24 at 12:06