next up previous contents
Next: Cotas inferiores Up: Sobre la Complejidad Previous: Primeros conceptos y

Cotas superiores en tiempo

Una gran parte de la investigación en Ciencias de la Computación consiste en diseñar y analizar algoritmos eficientes. Los algoritmos fundamentales (desde el punto de vista de la complejidad algorítmica) son de extremada importancia; proporcionan una forma sorprendentemente rápida de resolver una gran cantidad de problemas. Seguidamente analizamos la complejidad en tiempo de algunos de los más importantes. El parámetro n se refiere al tamaño de la entrada; y el tiempo es considerado en el peor de los casos y calculado sobre una máquina de Turing multicinta (o cualquier máquina de acceso aleatoria razonable) salvo cuando indiquemos lo contrario.

1. La transformada de Fourier, que requiere operaciones aritméticas, es una de las más usadas en las Ciencias de la Computación.

2. La multiplicación de grandes números. El método elemental requiere operaciones de bits para multiplicar dos números de n dígitos. En 1962 Karatsuba y Ofman publicaron un método que solo requiere pasos. Poco tiempo despues Toom (1963) demostró como construir circuitos Booleanos de tamaño con un arbitrariamente pequeño para llevar a cabo la multiplicación. En 1969 Cook y Aanderaa demostraron que la multiplicación requiere pasos usando una máquina de Turing clásica, cota que ha sido ligeramente mejorada. Por otro lado, el método de Toom puede adaptarse para multiplicar en una máquina de Turing multicinta en pasos.

El tiempo de ejecución asintótico más rápido para la multiplicación sobre una máquina de Turing multicinta es (obtenido por Schönhage y Strassen (1971) usando la transformada de Fourier). Sin embargo, Schönhage ha demostrado (1980) que su máquina de modificación de almacenamiento puede multiplicar en tiempo . La conclusión es clara, o bién la multiplicación es más fácil de lo que pensamos, o las máquinas de Schönhage son "demasiado" rápidas.

3. Multiplicación de Matrices. El método clásico requiere operaciones aritméticas para multiplicar dos matrices . Sorprendentemente Strassen (1969) publicó un método que solo requería operaciones. Se ha realizado mucho trabajo para intentar reducir el exponente , actualmente el mejor tiempo conocido es operaciones (Coppersmith y Winograd, 1982). Hay todavía un largo camino por recorrer, pues la mejor cota inferior conocida es .

4. Acoplamiento maximal en Grafos. Este fué quizas el primer problema para el que la demostración explícita de su pertenencia a P requiere un algoritmo muy complicado. El artículo de Edmonds citado anteriormente demostró el resultado y consideró la noción de algoritmo de tiempo polinomial.

5. Reconocimiento de números primos. La cuestión principal es si este problema esta o no en P. En otras palabras, ¿hay un algoritmo que dado un primo de n dígitos, pare en un número de pasos acotado por un polinomio en n? G. Miller (1976) demostró que tal algoritmo existe, pero su validez depende de la hipótesis de Riemann extendida. Solovay y Strassen (1977) encontraron un algoritmo de Monte Carlo rápido para el reconocimiento de números primos, pero si la entrada del algoritmo no es primo hay una pequeña probabilidad de que diga que es primo. El mejor algoritmo determinístico conocido es el de Adleman, Pomerance y Rumely (1983), y corre en tiempo , que es ligeramente peor que polinomial. Una variante de este, debida a H. Cohen y H.W. Lenstra (1982), corre con números de hasta 100 dígitos decimales en aproximadamente 45 segundos.

Ultimamente se ha demostrado que tres problemas importantes estan en la clase P. El primero es la programación lineal, demostrado por Khachian en 1979. El segundo es determinar si dos grafos de grado como mucho d son isomorfos, demostrado por Luks en 1980 (el algoritmo es polinomial sobre el número de vértices para un d fijo, pero exponencial en d). El tercero es la factorización de polinomios con coeficientes racionales, fue demostrado por Lenstra y Lovaz en 1982 para polinomios de una variable. La generalización para polinomios en cualquier número fijado de variables fue demostrada por Kaltofen en 1982.



next up previous contents
Next: Cotas inferiores Up: Sobre la Complejidad Previous: Primeros conceptos y




Thu Jan 11 11:00:25 WET 1996