Tiempo polinomial incremental

En complejidad computacional, el tiempo polinomial incremental (en inglés incremental polynomial delay) 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.^[1]

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

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.^[3]

Referencias

1. ↑ Makino, K; Ibaraki, T. (1997). «The maximum latency and identification of positive boolean functions» (en inglés). SIAM J. Comput 26. http://rutcor.rutgers.edu/pub/rrr/reports94/42.ps. Consultado el 31 de marzo de 2010. 
2. ↑ Johnson, D.S.; M.Yannakakis, C.Papadimitriou (1988). «On generating all maximal independent sets» (en inglés). Information Processing Letters 27 (3):  pp. 119-123. http://www.sciencedirect.com/science/article/pii/0020019088900658. 
3. ↑ Ramon, Jan; Nijssen, Siegfried (2009). «Polynomial-delay enumeration of monotonic graph classes» (en inglés). Journal of Machine Learning Research (JMLR.org) 10:  pp. 907-929. ISSN 1532-4435. http://jmlr.csail.mit.edu/papers/volume10/ramon09a/ramon09a.pdf.