Metraipolis › archive › dc_2a2d9b91c52c

Veintiún problemas NP-completos de Karp — Wikipedia (es)

Source
Wikipedia (es)
Original
https://es.wikipedia.org/wiki/Veinti%C3%BAn_problemas_NP-completos_de_Karp
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T23:29:49.844Z
SHA-256 of the archived text
1505422ee23a07b7bcc53f8ffc0979e32d6fd09178d4a5b08950af9e37443a2f
Stable URL of this page
https://metraipolis.com/documento/dc_2a2d9b91c52c

How to cite

Veintiún problemas NP-completos de Karp — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Veinti%C3%BAn_problemas_NP-completos_de_Karp (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2a2d9b91c52c (Metraipolis archive dc_2a2d9b91c52c, sha256 1505422ee23a07b7bcc53f8ffc0979e32d6fd09178d4a5b08950af9e37443a2f)
BibTeX
@misc{dc2a2d9b91c52c,
  title = {Veintiún problemas NP-completos de Karp — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Veinti%C3%BAn_problemas_NP-completos_de_Karp},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2a2d9b91c52c; sha256 1505422ee23a07b7bcc53f8ffc0979e32d6fd09178d4a5b08950af9e37443a2f},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Veinti%C3%BAn_problemas_NP-completos_de_Karp. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En teoría de complejidad computacional, los veintiún (21) problemas NP-completos de Karp son un conjunto de problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos. La demostración fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios), como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del problema de satisfacibilidad booleana. El descubrimiento de Karp de que todos estos importantes problemas eran NP-completos motivó el estudio de la NP-completitud y de la indagación en la famosa pregunta, de si P = NP.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»).
Fonte: Wikipedia in spagnolo, voce «Veintiún problemas NP-completos de Karp» — https://es.wikipedia.org/wiki/Veinti%C3%BAn_problemas_NP-completos_de_Karp
Wikidata Q1734364 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1734364
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Veinti%C3%BAn_problemas_NP-completos_de_Karp?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 173936645, consultata il 2026-10-07T23:08:54.904Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 708b4d7c73b8ac35e9781cec66caa2d1cd25086c6adf89566d843368bc1ab24d