This HTML5 document contains 22 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

PrefixNamespace IRI
category-eshttp://es.dbpedia.org/resource/Categoría:
dcthttp://purl.org/dc/terms/
n14http://es.wikipedia.org/wiki/Transformación_polinómica?oldid=120646567&ns=
wikipedia-eshttp://es.wikipedia.org/wiki/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n6http://rdf.freebase.com/ns/m.
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
Subject Item
dbr:Polynomial-time_reduction
owl:sameAs
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Transformación_polinómica
rdfs:label
Transformación polinómica
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 Σ*.
owl:sameAs
n6:01529y
dct:subject
category-es:Complejidad_computacional
foaf:isPrimaryTopicOf
wikipedia-es:Transformación_polinómica
dbo:wikiPageID
65540
dbo:wikiPageRevisionID
120646567
dbo:wikiPageInterLanguageLink
dbpedia-he:רדוקציה_חישובית
dbo:wikiPageLength
1326
prov:wasDerivedFrom
n14:0
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".
Subject Item
wikipedia-es:Transformación_polinómica
foaf:primaryTopic
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Reduccion_polinomial
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Reduccion_polinomica
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Reduccion_polinómica
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Reducción_polinomial
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Reducción_polinómica
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Transformacion_polinomial
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Transformacion_polinomica
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Transformacion_polinómica
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica
Subject Item
dbpedia-es:Transformación_polinomial
dbo:wikiPageRedirects
dbpedia-es:Transformación_polinómica