Linear speedup theorem explained

In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f(n), there is another k-tape machine that solves the same problem in time at most, where k > 1.[1] [2] If the original machine is non-deterministic, then the new machine is also non-deterministic.The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.[1]

Proof

The construction is based on packing several tape symbols of the original machine M into one tape symbol of the new machine N.It has a similar effect as using longer words and commands in processors: it speeds up the computations but increases the machine size.How many old symbols are packed into a new symbol depends on the desired speed-up.

Suppose the new machine packs three old symbols into a new symbol.Then the alphabet of the new machine is

\Sigma\cup\Sigma3

: it consists of the original symbols and the packed symbols.The new machine has the same number k > 1 of tapes.A state of N consists of the following components:

The new machine N starts with encoding the given input into a new alphabet (that is why its alphabet must include

\Sigma

).For example, if the input to 2-tape M is on the left, then after the encoding the tape configuration of N is on the right:
[# || _ || a || b || b || a || b || b || a || _ || ...]      [# || (_,_,_) || (_,_,_) || (_,_,_) || ...]
[# || _ || _ || _ || _ || _ || _ || _ || _ || _ || ...]      [# || (_,a,b) || (b,a,b) || (b,a,_) || ...]
The new machine packs three old symbols (e.g., the blank symbol _, the symbol a, and the symbol b) into a new symbol (here (_,a,b)) and copies it the second tape, while erasing the first tape.At the end of the initialization, the new machine directs its head to the beginning.Overall, this takes 2n + 3 steps.

After the initialization, the state of N is

(q0;~~~?,(\,\,\),?;~~~?,(\,a,b),?;~~~[1,1])

, where the symbol

?

means that it will be filled in by the machine later; the symbol

[1,1]

means that the head of the original machine points to the first symbols inside

(\,\,\)

and

(\,a,b)

. Now the machine starts simulating m = 3 transitions of M using six of its own transitions (in this concrete case, there will be no speed up, but in general m can be much larger than six).Let the configurations of M and N be:
[# || _ || _ || b || b || a || '''b''' || b || a || _ || ...]      [# || (_,a,b) || (b,a,b) || ('''b''',_,_) || ...]
[# || _ || a || b || '''b''' || a || b || b || _ || _ || ...]      [# || (_,_,'''b''') || (b,a,b) || (b,a,_) || ...]
where the bold symbols indicate the head position.The state of N is

(q;~~~?,(\,\,b),?;~~~?,(b,\,\),?;~~~[3,1])

.Now the following happens:

?

filled, and its state becomes

(q;~~~\#,(\,\,b),(b,a,b);~~~(b,a,b),(b,\,\),(\,\,\);~~~[3,1])

[# || _ || _ || _ || _ || _ || '''b''' || b || a || _ || ...]      [# || (_,a,b) || ('''b''',_,_) || (_,_,_) || ...]
[# || _ || a || b || '''b''' || _ || _ || _ || _ || _ || ...]      [# || (_,_,_) || (_,_,'''b''') || (b,a,_) || ...]
Thus, the state of N becomes

(q';~~~?,(\,\,b),?;~~~?,(b,\,\),?;~~~[3,1])

.

Complexity

Initialization requires 2n + 3 steps. In the simulation, 6 steps of N simulate m steps of M. Choosing m > 6c produces the running time bounded by

f(n)/c+2n+3.

Machines with a read-only input tape

The theorem as stated above also holds forTuring machines with 1-way, read-only input tapeand

k\ge1

work tapes.[3]

Single-tape machines

For single-tape Turing machines, linear speedup holds for machines with execution time at least

n2

. It provably does not hold for machines with time

t(n)\in\Omega(nlogn)\capo(n2)

.[3]

Dependence on tape compression

The proof of the speedup theorem clearly hinges on the capability to compress storage by replacing the alphabet with a larger one.Geffert[4] showed that fornondeterministic single-tape Turing machines of time complexity

T(n)\gen2

linear speedup can be achieved without increasing the alphabet.

Dependence on the shape of storage

Regan[5] considered a property of a computational model called information vicinity. This property is related to the memory structure: a Turing machine has linear vicinity, while a Kolmogorov-Uspenskii machine and other pointer machines have an exponential one. Regan’s thesis is that the existence of linear speedup has to do with having a polynomial information vicinity. The salient point in this claim is that a model with exponential vicinity will not have speedup even if changing the alphabet is allowed (for models with a discrete memory that stores symbols). Regan did not, however, prove any general theorem of this kind. Hühne [6] proved that if we require the speedup to be obtained by an on-line simulation (which is the case for the speedup on ordinary Turing machines), then linear speedup does not exist on machines with tree storage.

Notes and References

  1. Book: Christos Papadimitriou. Christos Papadimitriou. Computational Complexity . 2.4. Linear speedup . Addison-Wesley . 1994.
  2. Book: Thomas A. Sudkamp. Thomas A. Sudkamp. Languages and Machines: An Introduction to the Theory of Computer Science . 14.2 Linear Speedup . Addison-Wesley . 1994.
  3. Book: Wagner . K. . Wechsung . G. . Computational Complexity . 1986 . Springer . 978-9027721464.
  4. Geffert . Viliam . A speed-up theorem without tape compression . Theoretical Computer Science . 1993 . 118 . 1 . 49–65 . 10.1016/0304-3975(93)90362-W. free .
  5. Regan . Kenneth W. . Linear time and memory-efficient computation . SIAM Journal on Computing . 1996 . 25 . 1 . 133–168.
  6. Hühne . Martin . Linear Speed-Up Does not Hold on Turing Machines with Tree Storages . Information Processing Letters . 1993 . 47 . 6 . 313–318 . 10.1016/0020-0190(93)90078-N.