Teorema del aumento de velocidad
- 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)).
Categoría:
- Teoremas de complejidad computacional
Wikimedia foundation.
2010.
Mira otros diccionarios:
Teorema del aumento de velocidad lineal — Saltar a navegación, búsqueda En Teoría de la complejidad computacional, el teorema del aumento de velocidad lineal por máquinas de Turing es el siguiente: Dado c > 0 y cualquier máquina de Turing que resuelve un problema en tiempo , hay otra… … Wikipedia Español
Teorema del aumento de velocidad de Blum — En Teoría de la complejidad computacional el teorema del aumento de velocidad de Blum, dado primero por Manuel Blum en 1967, es un teorema importante sobre la complejidad de funciones computables. Cada función computable tiene un número infinito… … Wikipedia Español
Teorema del incremento lineal de velocidad — El teorema del incremento lineal de velocidad de las máquinas de Turing es un teorema de teoría de la complejidad computacional, que se puede enunciar: Dado c > 0 y cualquier máquina de Turing que resuelve un problema en tiempo , hay otra… … Wikipedia Español
Teorema de Bell — El teorema de Bell o desigualdades de Bell se aplica en mecánica cuántica para cuantificar matemáticamente las implicaciones planteadas teóricamente en la paradoja de Einstein Podolsky Rosen y permitir así su demostración experimental. Debe su… … Wikipedia Español
Teorema de las fuerzas vivas — El teorema de las fuerzas vivas es un teorema importante en el contexto de la mecánica clásica, en especial dentro del campo de la dinámica y de los análisis energéticos. También es conocido como teorema de la energía cinética. Contenido 1… … Wikipedia Español
Historia del electromagnetismo — La Historia del electromagnetismo, que es el conocimiento y el uso registrado de las fuerzas electromagnéticas, data de hace más de dos mil años. En la antigüedad ya estaban familiarizados con los efectos de la electricidad atmosférica, en… … Wikipedia Español
Problemas no resueltos de la informática — Los siguientes son algunos de los problemas no resueltos de las Ciencias de la Computación. Una solución de los problemas de esta lista tendría un impacto notable en el campo de estudio al que pertenecen. Contenido 1 Teoría de Complejidad… … Wikipedia Español
Filosofía del espacio y el tiempo — Saltar a navegación, búsqueda La filosofía del espacio y el tiempo es la rama de la filosofía que trata de los aspectos referidos a la ontología, la epistemología y la naturaleza del espacio y el tiempo, lo que se conoce también como cosmología.… … Wikipedia Español
Flujo sanguíneo — Saltar a navegación, búsqueda Contenido 1 Definición. 2 Introducción 2.1 Valores normales en el humano 2.2 Índice c … Wikipedia Español
Cálculo — Saltar a navegación, búsqueda Para otros usos de este término, véase Cálculo (desambiguación). Para cálculo infinitesimal (diferencial o integral) véase Cálculo infinitesimal Para el estudio de los números reales, los complejos, los vectores y… … Wikipedia Español
