| Property |
Value |
| dbo:abstract
|
- En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo. Formalmente, sean L y M lenguajes formales sobre los alfabetos Σ y Γ, respectivamente, una transformación polinómica de L en M es una función computable: que puede ser calculada en tiempo polinómico en función del tamaño de la entrada, y que está definida por: para todo elemento w de Σ*. Cuando esta función f existe, se dice que "L es polinómicamente transformable en M". (es)
- En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo. Formalmente, sean L y M lenguajes formales sobre los alfabetos Σ y Γ, respectivamente, una transformación polinómica de L en M es una función computable: que puede ser calculada en tiempo polinómico en función del tamaño de la entrada, y que está definida por: para todo elemento w de Σ*. Cuando esta función f existe, se dice que "L es polinómicamente transformable en M". (es)
|
| dbo:wikiPageID
| |
| dbo:wikiPageInterLanguageLink
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| dct:subject
| |
| rdfs:comment
|
- En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo. Formalmente, sean L y M lenguajes formales sobre los alfabetos Σ y Γ, respectivamente, una transformación polinómica de L en M es una función computable: para todo elemento w de Σ*. (es)
- En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo. Formalmente, sean L y M lenguajes formales sobre los alfabetos Σ y Γ, respectivamente, una transformación polinómica de L en M es una función computable: para todo elemento w de Σ*. (es)
|
| rdfs:label
|
- Transformación polinómica (es)
- Transformación polinómica (es)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
