| dbo:abstract
|
- 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 (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 (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. (es)
- 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 (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 (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. (es)
|
| rdfs:comment
|
- 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. (es)
- 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. (es)
|
