Back Karps 21 NP-vollständige Probleme German Karp's 21 NP-complete problems English Veintiún problemas NP-completos de Karp Spanish ۲۱ مسئله انپی-کامل کارپ Persian 21 problèmes NP-complets de Karp French 21 הבעיות ה-NP שלמות של קארפ HE 21 problemi NP-completi di Karp Italian Karps 21 NP-volledige problemen Dutch Cele 21 de probleme NP-complete ale lui Karp Romanian Список Карпа Russian
Na teoria da complexidade computacional, os 21 problemas NP-completos de Karp é um conjunto de problemas computacionais que são NP-completos. Em seu artigo de 1972, "Reducibility among Combinatorial Problems",[1] Richard Karp usou o teorema de que o problema da satisfatibilidade é NP-completo[2] de Stephen Cook publicado em 1971 (também chamado teorema de Cook-Levin), para mostrar que existe uma redução por mapeamento em tempo polinomial do problema de satisfatibilidade para cada uma das 21 dos problemas computacionais de combinatória e da teoria dos grafos, mostrando assim que todos eles são NP-completos. Esta foi uma das primeiras demonstrações de que muitos problemas computacionais naturais que ocorrem ao longo da ciência da computação são computacionalmente intratáveis, e aumentou o interesse no estudo da NP-completude e do problema "P vs NP".
- ↑ Karp, Richard M. (1972). Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D., eds. «Reducibility among Combinatorial Problems». Boston, MA: Springer US. The IBM Research Symposia Series (em inglês): 85–103. ISBN 978-1-4684-2001-2. doi:10.1007/978-1-4684-2001-2_9. Consultado em 29 de outubro de 2023
- ↑ Cook, Stephen A. (3 de maio de 1971). «The complexity of theorem-proving procedures». New York, NY, USA: Association for Computing Machinery. STOC '71: 151–158. ISBN 978-1-4503-7464-4. doi:10.1145/800157.805047. Consultado em 29 de outubro de 2023