En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: El Problema de satisfacibilidad booleana (SAT) es NP-completo. Stephen Cook (1971) Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures". El teorema fue demostrado independientemente por Leonid Levin aproximadamente en la misma fecha, por lo que algunas veces es llamado Teorema de Cook-Levin.
rdfs:comment |
|
foaf:isPrimaryTopicOf | |
rdfs:label |
|
Is foaf:primaryTopic of | |
dcterms:subject | |
prov:wasDerivedFrom | |
dbpedia-owl:wikiPageID |
|
dbpedia-owl:wikiPageLength |
|
dbpedia-owl:wikiPageOutDegree |
|
Is dbpedia-owl:wikiPageRedirects of | |
dbpedia-owl:wikiPageRevisionID |
|
prop-latam:wikiPageUsesTemplate | |
dbpedia-owl:wikiPageWikiLink | [22 values] |
Is dbpedia-owl:wikiPageWikiLink of |