0
$\begingroup$

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 ?

Improve this question
$\endgroup$
9
  • $\begingroup$ Another assumption in what theorem? You didn’t formulate any theorem. $\endgroup$
    – Emil Jeřábek
    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$
    – Omid Yaghoubi
    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$
    – Emil Jeřábek
    Jun 23, 2022 at 6:15
  • $\begingroup$ @EmilJeřábek Thanks ! $\endgroup$
    – Omid Yaghoubi
    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$
    – Emil Jeřábek
    Jun 24, 2022 at 12:06

0

Reset to default

Your Answer

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