Situación de compromiso espacio-tiempo

En Informática, el compromiso espacio-tiempo o tiempo-memoria es una situación en la que la memoria puede reducirse a costa de la ejecución más lenta de los programas, o viceversa, el tiempo de ejecución puede reducirse a costa de incrementar el uso de memoria. En la medida en que cambian los costos relativos de los ciclos de CPU, espacio en RAM y espacio en disco duro —durante algún tiempo el espacio en disco duro se ha estado abaratando a un ritmo mucho más rápido que otros componentes de los ordenadores ^{[cita requerida]}— la elección apropiada en soluciones de compromiso espacio-tiempo ha cambiado radicalmente. A menudo, aprovechando una situación de compromiso tiempo-memoria, la clase de complejidad de un problema puede cambiar por completo.

La situación más común es un algoritmo que utiliza una tabla de búsqueda: una implementación puede incluir la tabla al completo, lo que reduce el tiempo de ejecución, pero incrementa la cantidad de memoria necesitada, o puede calcular entradas de la tabla a medida que se necesiten, incrementando el tiempo de ejecución, pero reduciendo los requisitos de memoria.

El compromiso espacio-tiempo se puede aplicar al simple problema de almacenamiento de datos. Si los datos se almacenan de forma no comprimida se necesita más espacio pero menos tiempo que si los datos se almacenan de forma comprimida (ya que la compresión reduce la cantidad de espacio utilizado, pero utiliza tiempo de ejecución para procesar el algoritmo de compresión). Dependiendo del caso concreto de problema será o no práctico.

Otro ejemplo es la presentación de fórmulas matemáticas en sitios Web basados principalmente en texto, como la Wikipedia. Almacenar únicamente el código fuente LaTeX y transformarlo a una imagen cada vez que se solicita la página sería una solución de compromiso de tiempo frente a memoria —se utiliza más tiempo pero menos memoria. Transformar la imagen cuando se guarda la página de manera que queden almacenadas sería una solución de compromiso de memoria frente al tiempo - se utiliza más memoria pero menos tiempo.

Entre los algoritmos que usan soluciones de compromiso espacio-tiempo para conseguir mejores tiempos de ejecución se incluye el algoritmo de paso-de-niño paso-de-gigante para calcular logaritmos discretos.

En otras áreas, el compromiso espacio-tiempo puede darse cuando se llevan a cabo ataques de fuerza bruta contra criptosistemas mediante la creación de tablas arcoiris. El ataque Meet-in-the-middle es una aplicación de situaciones de compromiso espacio-tiempo.

Enlaces externos

• Making a Faster Cryptanalytic Time-Memory Trade-Off - Philippe Oechslin (en inglés)
• Once Upon a Time-Memory Tradeoff (en inglés)
• Password Cracking and Time-Memory Trade Off (en inglés)
• A cryptanalytic time-memory trade-off - Martin Hellman (en inglés)
• Les compromis temps-mémoire et leur utilisation pour casser les mots de passe Windows - Philippe Oechlin (conférence SSTIC 2004) (en francés)