En el análisis de algoritmos , se dice que un algoritmo de enumeración (es decir, un algoritmo para enumerar una colección grande o infinita de estructuras) tiene un retraso polinomial si el tiempo entre la salida de cualquier estructura y la siguiente está limitado por una función polinomial de el tamaño de entrada, en el peor de los casos . [1] El retraso polinomial implica que el tiempo total utilizado por un algoritmo será polinomial por elemento de salida, pero es un requisito más fuerte. Esta es una propiedad deseable, porque significa que cualquier consumidor del flujo de salidas no tendrá que esperar inactivo durante mucho tiempo de una salida a la siguiente. En particular, un algoritmo con retraso polinomial no puede tener una fase de inicio que tometiempo exponencial antes de que produzca una sola salida, a diferencia de algunos algoritmos que toman tiempo polinomial por elemento de salida. [2] Además, a diferencia de los límites en el tiempo total, es una forma adecuada de análisis incluso para algoritmos que producen una secuencia infinita de resultados.
La noción de retraso polinomial fue introducida por primera vez por David S. Johnson , Mihalis Yannakakis y Christos Papadimitriou . [2]