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.[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]
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.[2]
Conjuntos
editarUn 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
editar- ↑ Makino, K; Ibaraki, T. (1997). «The maximum latency and identification of positive boolean functions». SIAM J. Comput (en inglés) 26. Consultado el 31 de marzo de 2010.
- ↑ a b Johnson, D.S.; M.Yannakakis, C.Papadimitriou (1988). «On generating all maximal independent sets». Information Processing Letters (en inglés) 27 (3): 119-123.
- ↑ Ramon, Jan; Nijssen, Siegfried (2009). «Polynomial-delay enumeration of monotonic graph classes». Journal of Machine Learning Research (en inglés) (JMLR.org) 10: 907-929. ISSN 1532-4435.
Datos: Q6146535
