Teorema da aceleração linear

O teorema da aceleração linear ou speedup linear é um teorema da teoria da complexidade, um campo da teoria da computação. Pode-se distinguir dois teoremas: uma que diz respeito às classes de complexidade referentes ao espaço e outro que diz respeito às classes de complexidade de tempo. Ambos têm como consequência agrupar as medidas de complexidade que diferem apenas por uma constante, e, portanto, justifica a notação O utilizada no campo.

O teorema da aceleração do tempo foi provado por Juris Hartmanis e Richard Stearns.

Enunciados

Teorema da aceleração do tempo

Para qualquer máquina de Turing ${\displaystyle }$ que calcula uma função ${\displaystyle }$ em tempo  ${\displaystyle }$ (sendo ${\displaystyle }$ o tamanho da entrada) e qualquer constante ${\displaystyle }$, existe uma máquina de Turing ${\displaystyle }$ que calcula  ${\displaystyle }$ em tempo  ${\displaystyle }$.

Teorema da aceleração no espaço

Para qualquer máquina de Turing ${\displaystyle }$ que calcula uma função ${\displaystyle }$ com uso de espaço limitado por ${\displaystyle }$ (sendo ${\displaystyle }$ o tamanho da entrada) e qualquer constante ${\displaystyle }$, existe uma máquina de Turing ${\displaystyle }$ que calcula ${\displaystyle }$ usando espaço limitado por ${\displaystyle }$.

Esboço da prova

A ideia principal da prova é codificar vários símbolos da máquina de Turing T em um único símbolo da máquina de Turing T': agrupando símbolos, pode-se usar menos espaço e "saltar" de um grupo de letras para outro, o que leva menos tempo. Fazendo grupos de 1/c letras, obtemos o resultado anunciado.

A ideia é simplesmente que, mais de um cálculo pode ser feito em uma única etapa de cálculo. Isto é comparável a alteração de tamanho dos registradores da cpu de 32 para 64 bits.

Consequências

Esses resultados são usados para justificar o fato de as constantes multiplicativas não serem levadas em consideração na teoria da complexidade computacional.