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 ?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.