Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Is there an algorithm for the following problem:
Given a Turing machine $M_1$ that decides a language $L$,
Is there a Turing machine $M_2$ deciding $L$ such that $t_2(n) = o(t_1(n))$?
The functions $t_1$ and $t_2$ are the worst-case running times of Turing machines $M_1$ and $M_2$ respectively.
What about space complexity?
Here is a simple argument to show that they are undecidable, i.e. there are no algorithms to check if a given algorithm is optimal regarding its running-time or memory usage.
We reduce the halting problem on blank tape to your problem about running-time optimality.
Let $M$ be a given Turing machine. Let N be the following Turing machine:
$N$: on input $n$
1. Run $M$ on blank tape for (at most) $n$ steps.
2. If $M$ does not halt in $n$ steps, run a loop of size $2^n$, then return NO.
3. Otherwise, return YES.
There are two cases:
If $M$ does not halt on blank tape, the machine $N$ will run for $\Theta(2^n)$ steps on input $n$. So its running time is $\Theta(2^n)$. In this case, $N$ is obviously not optimal.
If $M$ halts on blank tape, then machine $N$ will run for constant number of steps for all large enough $n$, so the running time is $O(1)$. In this case, $N$ is obviously optimal.
In short:
$$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$$
Moreover given the code for $M$ we can compute the code for $N$. Therefore we have reduction from halting problem on blank tape to running-time optimality problem. If we could decide if a given Turing machine $N$ is optimal, we could use the above reduction to check if a given machine $M$ halts on blank tape. Since halting on blank tape is unecidable your problem is also undecidable.
A similar argument can be used for space, i.e. it is also undecidable to check if a given Turing machine is optimal regarding the space it uses.
Even a stronger statement is true: we can't decide if a given computable function is an upper-bound on the time complexity of computing a given computable function. Similarly for space. I.e. even basic complexity theory cannot be automatized by algorithms (which can be considered a good news for complexity theorists ;).
As others mentioned the answer is no.
But there is an interesting article written by Blum "A Machine-Independent theory of the Complexity of Recursive Functions". He showed that there are some functions with the property that no matter how fast a program may be for computing these functions another program exists for computing them very much faster.
a very nice property!
Ha! Were the answer yes, we would be living in a different world.
Imagine that the answer to your question was yes (and of course we knew the algorithm $A_0$ that would answer your question), then for any algorithm $A$ for language $L$, we would be able to tell (using $A_0$) if $A$ is optimal or not.
Unfortunately, this is not possible, and indeed I personally think proving (non-trivial) optimality is the most interesting (and difficult) problem in computer science. As far as I know - I would be glad to be corrected - there exists no optimality result for any polynomial problem (except the trivial optimality results of course of algorithms taking time proportional to input size).
