Retraso polinomial

En el análisis de algoritmos , se dice que un algoritmo de enumeración (es decir, un algoritmo para listar una colección grande o infinita de estructuras) tiene retardo 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 retardo polinomial implica que el tiempo total empleado por un algoritmo será polinomial por elemento de salida, pero es un requisito más estricto. Esta es una propiedad deseable, porque significa que cualquier consumidor del flujo de salidas no tendrá que esperar inactivo durante mucho tiempo entre una salida y la siguiente. En particular, un algoritmo con retardo 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 de análisis adecuada incluso para algoritmos que producen una secuencia infinita de salidas.

La noción de retardo polinomial fue introducida por primera vez por David S. Johnson , Mihalis Yannakakis y Christos Papadimitriou . ^{[ 2 ]}