Una escalada en los recursos computacionales requeridos (tiempo, memoria, espacio intermedio) causada por características sintácticas, codificaciones, elecciones algorítmicas o instancias de problema específicas que hacen que el cálculo sea impracticable.

Principio

Ciertas codificaciones o transformaciones pueden aumentar el tamaño de la representación o las estructuras intermedias (por ejemplo, duplicar subexpresiones o expandir cuantificadores), y los procesos algorítmicos pueden tener un uso de recursos en el peor caso que crece superpolinomialmente con el tamaño de la entrada.

Demostración

Convertir una fórmula a forma normal disyuntiva (FND) puede inflar exponencialmente su longitud; la expansión ávida de definiciones o el grounding ingenuo de fórmulas cuantificadas en un dominio grande puede agotar memoria y tiempo aun cuando la especificación original sea compacta.

Aplicación incorrecta

Elegir codificaciones o algoritmos que materialicen implícitamente un número exponencial de resultados intermedios (por ejemplo, expandir completamente construcciones combinatorias) bajo la suposición de que el tamaño del problema permanecerá pequeño, lo que conduce a fallos del sistema o tiempos de ejecución incontrolables.

Consecuencia

La concienciación sobre la explosión de recursos conduce a codificaciones alternativas, evaluación perezosa, representaciones simbólicas, streaming o aproximación; cuando se aborda correctamente, restaura la viabilidad y límites de recursos previsibles para casos de uso previstos.

Inversión

Contención de recursos — elecciones algorítmicas y de representación que mantienen tiempo y espacio dentro de límites aceptables (p. ej., codificaciones en tiempo polinómico, algoritmos en streaming, métodos incrementales).

Límite

Se refiere a costes de recursos derivados de representaciones, codificaciones o expansiones algorítmicas; distinto de la mera clasificación de complejidad algorítmica (p. ej., P frente a NP) en la medida en que la explosión suele originarse en codificaciones o preprocesos particulares más que en la complejidad inherente de decisión.

Tensión semántica

Estrechamente relacionado con la explosión del espacio de búsqueda: uno describe el crecimiento combinatorio de candidatos, el otro enfatiza los recursos realmente consumidos; las técnicas de mitigación se solapan pero pueden priorizar el diseño de memoria, streaming y evaluación incremental sobre heurísticas de búsqueda.

Síntesis

La explosión de recursos es el modo de fallo práctico en el que representaciones o pasos algorítmicos generan demandas de tiempo o memoria prohibitivas; resolverla requiere elegir codificaciones y estrategias de evaluación que eviten materializar grandes estructuras intermedias y explotar pereza, modularidad o aproximación.