title: Tiempo polinómico incremental
text: # 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.
  
  