1
$\begingroup$

Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

For example, is it possible to find a primitive recursive function such that:

  • The fastest primitive recursive program to compute it runs in $O(f(N))$.
  • The fastest non primitive recursive (for example doubly recursive) program to compute it runs in $O(g(N))$.
  • $O(g(N)) < O(f(N))$ i.e. the complex program is faster than the simple one.

I can't find the correct terminology for "primitive recursive program", since those words usually refer to functions themselves. That is why I use "ordinal complexity" instead, as defined here for example.

$\endgroup$
8
  • $\begingroup$ I think I can prove this is impossible, but with one assumption: that your programming language has the equivalent of a "break" statement. In other words, you can start a loop of, say, $N^3$ iterations, but then break it early, spending much less than $O(N^3)$ time. $\endgroup$ Sep 14, 2023 at 12:26
  • $\begingroup$ So, if there was an example of this paradoxical behavior, but it could only occur in a language without a "break" statement, would that count as "interesting" for you? Or would that be too unrealistic? $\endgroup$ Sep 14, 2023 at 12:28
  • $\begingroup$ I assume the programming language is Turing complete. $\endgroup$
    – agemO
    Sep 14, 2023 at 13:15
  • $\begingroup$ But here the problem is about the fastest programs that can compute a given function, but I agree that your comment would technically answer the title alone. $\endgroup$
    – agemO
    Sep 14, 2023 at 13:18
  • $\begingroup$ "Turing complete" doesn't tell me much. My question is about running time, which has nothing to do with Turing completeness. $\endgroup$ Sep 14, 2023 at 14:24

1 Answer 1

2
$\begingroup$

Okay, as discussed in the comments, I will be assuming that the programming language has something like a "break" statement, which completely skips all the remaining iterations of a loop, spending $O(1)$ time on them, no matter how many iterations were remaining.

Let $M$ be an abstract machine (a Turing machine, a RAM machine, whatever is more convenient) which calculates our function by the non-primitive-recursive way. The point is, the running time of $M$ is $O(g(N))$.

Write a primitive-recursive program that does the following:

  • Create a simulation of $M$ in its initial state, ready to run.
  • Calculate our function in a primitive-recursive way (with $O(f(N))$ complexity), EXCEPT:
    • After each and every every step of this calculation, do the following:
      • Advance the simulation of $M$ by one step.
        • (Doing one step of a machine should be an $O(1)$ operation.)
      • If it turns out that $M$ is in its finished state, then:
        • break out of all the loops, stop the calculation, return the result that $M$ has inside it.
  • If the calculation has finished while $M$ is still not done, forget about it and return the result we have calculated.

This program is "supposed to" do $O(f(N))$ operations, but if $N$ is large enough, then $M$ will finish first, and the program will return early after just $O(g(N))$ operations. Therefore, the asymptotic complexity of this thing is $O(g(N))$.

In summary: if you have a non-primitive-recursive solution for a problem, as well as a worse primitive-recursive solution, then you can rewrite the better solution in a primitive-recursive way. So the "inversion" of complexities is impossible.

(Really, the main purpose of the worse solution is merely to wait an appropriate amount of steps for the machine to complete. If we had a perfect predictor of how long the machine would take, then we wouldn't need the worse solution at all. But here, I'm using it as a backup, in case my estimation of the running time was too low.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.