Tiempo polinómico incremental
# Tiempo polinómico incremental

En complejidad computacional, el tiempo polinómica incremental (en inglés, incremental polynomial time) se refiere a cuando el tiempo de ejecución de un algoritmo de enumeración de un conjunto es polinomial en términos de la entrada y de los elementos de la salida hasta ahora computados.

Este término fue definido por primera vez en 1988 por los informáticos teóricos David S. Johnson, Mihalis Yannakakis y Christos Papadimitriou.

Si un algoritmo es polinómico incremental, entonces también es total polinomial (en inglés, tiene polynomial total time), es decir, el tiempo total requerido para arrojar la salida está acotado por un polinomio en función del tamaño de la entrada y del número de configuraciones que conforman dicha salida. Una condición más fuerte es que el algoritmo tenga retardo polinomial (polynomial delay), esto es, que el tiempo necesario para encontrar cada nueva configuración esté acotado por un polinomio únicamente en función del tamaño del input.

## Conjuntos

Un conjunto es polinomial incrementalmente numerable (en inglés el término se conoce como polynomial delay enumeration) si se puede construir un algoritmo que sea capaz de ir generando todos sus elementos, de modo que cada iteración del algoritmo está polinomialmente acotada.

