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

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

Subject Item

wikipedia-es:Co-NP

foaf:primaryTopic

dbpedia-es:Co-NP

Subject Item

dbpedia-es:Co-NP

rdfs:label

Co-NP

rdfs:comment

En teoría de la complejidad computacional, la clase de complejidad co-NP es el conjunto de los problemas de decisión complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa están invertidas. La clase de complejidad P es un subconjunto tanto de NP como de co-NP y se piensa que la inclusión es estricta en ambos casos. Se piensa también que NP y co-NP son diferentes. De ser cierto esto, ningún problema de NP-completo podría estar en co-NP y ningún problema de co-NP-completo podría estar en NP. * Datos: Q955748

owl:sameAs

n6:01v72

dct:subject

category-es:Clases_de_complejidad category-es:Problemas_no_resueltos_de_las_ciencias_de_la_computación

foaf:isPrimaryTopicOf

wikipedia-es:Co-NP

dbo:wikiPageID

65939

dbo:wikiPageRevisionID

117254379

dbo:wikiPageLength

1412

prov:wasDerivedFrom

n4:0

dbo:abstract

En teoría de la complejidad computacional, la clase de complejidad co-NP es el conjunto de los problemas de decisión complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa están invertidas. La clase de complejidad P es un subconjunto tanto de NP como de co-NP y se piensa que la inclusión es estricta en ambos casos. Se piensa también que NP y co-NP son diferentes. De ser cierto esto, ningún problema de NP-completo podría estar en co-NP y ningún problema de co-NP-completo podría estar en NP. Esto se demuestra como sigue: Si hubiera un problema en NP-completo y en co-NP al mismo tiempo, todo problema de NP se reduciría en él, se deduce que para todo problema en NP se podría construir una máquina de Turing no determinista que decidiera el problema complementario en tiempo polinómico, es decir, NP sería un subconjunto de co-NP y, por tanto los complementos de NP serían subconjunto de los complementos de co-NP, es decir, co-NP sería un subconjunto de NP, Por tanto NP y co-NP serían el mismo conjunto. De forma simétrica se demuestra que ningún problema en co-NP-completo puede estar en NP. * Datos: Q955748

Subject Item

dbpedia-es:CoNP

dbo:wikiPageRedirects

dbpedia-es:Co-NP

Subject Item

dbpedia-es:Co_NP

dbo:wikiPageRedirects

dbpedia-es:Co-NP

Subject Item

dbr:Co-NP

owl:sameAs

dbpedia-es:Co-NP