Speedup-Theorem

In complexity theory, various speed-up theorems are used (acceleration rates) for evidence that a machine or an algorithm can be speeded up by a certain factor, if already known a different machine or a different algorithm.

The original version of the speedup theorem comes from Manuel Blum ( 1967), but today it is because of the use of any complexity functions are no longer of great importance. It is now in complexity theory in general true complexity of advance features that must fulfill certain properties (see also requirements for barrier functions).

Linear speedup theorem

The best known representative is the linear speedup theorem, which is also referred to as a linear acceleration. The linear speedup theorem states that, can construct a new Turing machine at any Turing machine that computes a problem in duration, having calculated the problem in time. This means simplistically that every Turing machine that solves a specific problem in a specific time to be accelerated any linear factor. The extra addition of ( n 2 ) arises from the need to fully read the input word of the source machine.

The ability to accelerate Turing machine owes you the free choice of the working alphabet of the machine. Characterized a plurality of memory cells can be combined by being represented by a cell (volume compression).

Other speedup theorems are the speedup theorem of Blum and the quadratic speedup theorem.

Example from mathematics

The addition of binary numbers 1001101 and 1010011 requires an addition step per each pair of digits. Altogether seven. If one writes the numbers in the decimal system (77 and 83 ) so you only need two additions - but with larger numbers. It should be noted that it is not always possible to accelerate computing a specific example by a linear factor, but belonging to the addition Turing machine for arbitrarily large inputs.

The example also explains why programs can not be accelerated in this manner on real computers. Unlike a Turing machine can not process a different alphabet except binary calculator.

• Computability theory