11
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ The answer is definitely not. Determining the worst-case running time of a TM is known to be undecidable. $\endgroup$
    – chazisop
    Feb 1, 2013 at 9:51
  • $\begingroup$ More general question. $\endgroup$
    – Raphael
    Feb 15, 2015 at 9:35

3 Answers 3

9
$\begingroup$

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:

  1. 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.

  2. 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 ;).

$\endgroup$
4
  • $\begingroup$ Just want to mention that in the original question, OP assumed that $M_1$ decides the language in quadratic time. $\endgroup$
    – Pål GD
    Feb 2, 2013 at 12:52
  • $\begingroup$ Please clarify that you look at asymptotic optimality. Even in case 2, $n$ is not strictly optimal; the function $n \mapsto \textrm{YES}$ can be computed in one step, whereas $N$ needs more than $n_0$ (for large $n$), with $n_0$ the length of the computation of $M$ on blank tape. $\endgroup$
    – Raphael
    Feb 2, 2013 at 14:12
  • $\begingroup$ Ah, the question changed since I last read it. Never mind. $\endgroup$
    – Raphael
    Feb 2, 2013 at 14:13
  • $\begingroup$ @PålGD, I think OP used that as an example (based on the original question posted on cstheory). You can check the comments under that question. $\endgroup$
    – Kaveh
    Feb 2, 2013 at 14:52
2
$\begingroup$

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!

$\endgroup$
-3
$\begingroup$

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).

$\endgroup$
13
  • 1
    $\begingroup$ For some problems there are known bounds of the form $\Omega(N)$, and algorithms which satisfy this. Simple examples are e.g., sorting by comparison, finding the least element of an array. $\endgroup$
    – vonbrand
    Jan 31, 2013 at 20:28
  • 1
    $\begingroup$ First, "asymptotically optimal" is not the same as "optimal". Second, you don't answer the question. Third, there are $\Omega(n \log n)$ lower bounds for (certain kinds of) sorting algorithms. $\endgroup$
    – Raphael
    Feb 1, 2013 at 10:56
  • $\begingroup$ @vonbrand - that's what I meant by algorithms taking proportional to input size. $\endgroup$
    – t to the t
    Feb 1, 2013 at 13:42
  • 1
    $\begingroup$ @ttothet Ok, I'm afraid it will be fruitless but I'll try again. 1) No, not at all. If you save only one step on every input, you have a better algorithm than before, even though it has the same asymptotic runtime. 2) No, it does not. It can also mean "I don't know, but if yes, then X". This is not uncommon (cf P?=NP). 3) You claimed there were no non-trivial lower bounds (on asymptotics, I assume) at all. That is wrong. Do your homework, please. $\endgroup$
    – Raphael
    Feb 1, 2013 at 13:50
  • 1
    $\begingroup$ @MartinJonáš I mean a 2-tape Turing machine. Kaveh has a point, the proof of the time hierarchy theorem does give polytime solvable problems with arbitrarily high complexity, but the examples are not exactly natural and don't feel very explicit. Also, no hierarchy is known for probabilistic time, so there we really have nothing. $\endgroup$ Feb 3, 2013 at 2:14

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.

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