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 del tamaño de la 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 desde una salida a la siguiente. En particular, un algoritmo con retraso polinomial no puede tener una fase de inicio que tome un tiempo exponencial antes de producir una sola salida, a diferencia de algunos algoritmos que toman un 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 salidas.
El concepto de retraso polinomial fue introducido por primera vez por David S. Johnson , Mihalis Yannakakis y Christos Papadimitriou . [2]