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[1].
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 [2].
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 idéia 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[3].
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 computácional.
Notas e referências
- ↑ (en) Sanjeev Arora e Boaz Barak, Complexidade Computacional : Uma Abordagem moderna, Cambridge University Press, (ISBN 0-521-42426-7)
- ↑ (en) Christos Papadimitriou, Complexidade Computacional, Addison-Wesley, (ISBN 978-0-201-53082-7) capítulo 2.4.
- ↑ Sylvain Perifel, Complexidade de algoritmos, Elipses, , 432 p.