Teorema del aumento de velocidad
En la teoría de la complejidad computacional, un teorema del aumento de velocidad es un teorema que considera un algoritmo que resuelva un problema y demuestra que existe otro algoritmo más rápido que resuelve el mismo problema (o, más generalmente, un algoritmo que utiliza una menor cantidad de cualquier recurso, no solo tiempo).
El teorema del aumento de velocidad lineal para máquinas de Turing prueba que dado cualquier máquina que resuelva un problema usando f(n) de un recurso, existe otra máquina que lo resuelve utilizando cf(n) de ese mismo recurso, donde c > 0.
El teorema del aumento de velocidad de Blum prueba la existencia de un problema tal que si existe un algoritmo que puede resolverlo en tiempo O(f(n)), entonces existe otro algoritmo que lo resuelve en tiempo O(log f(n)).
El Teorema del aumento de velocidad cuadrátido para una computadora cuántica prueba que si una computadora determinista puede efectuar una búsqueda en tiempo O(f(n)), entonces una computadora cuántica puede efectuar la misma búsqueda en tiempo O(√f(n)).