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.(en) Sanjeev Arora e Boaz Barak, Complexidade Computacional : Uma Abordagem moderna, Cambridge University Press, 2009 ()
Enunciados
Teorema da aceleração do tempo Para qualquer máquina de Turing que calcula uma função em tempo (sendo o tamanho da entrada) e qualquer constante , existe uma máquina de Turing que calcula em tempo .(en) Christos Papadimitriou, Complexidade Computacional, Addison-Wesley, 1993 () capítulo 2.4.
Teorema da aceleração no espaço Para qualquer máquina de Turing que calcula uma função com uso de espaço limitado por (sendo o tamanho da entrada) e qualquer constante , existe uma máquina de Turing que calcula usando espaço limitado por .
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.Sylvain Perifel, Complexidade de algoritmos, Elipses, 2014, 432 p.
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.
Notas e referências
Categoria:Teoria da complexidade computacional