b'\n_START_ARTICLE_\n21 problemas NP-completos de Karp\n_START_PARAGRAPH_\nNa teoria da complexidade computacional, os 21 problemas NP-completos de\xc2\xa0Karp \xc2\xa0\xc3\xa9 um conjunto de problemas computacionais que s\xc3\xa3o NP-completos. Em seu artigo de 1972, "Reducibility Among Combinatorial Problems",  Richard Karp usou\xc2\xa0o teorema de que \xc2\xa0o problema da satisfatibilidade\xc2\xa0\xc3\xa9 NP-completo\xc2\xa0de Stephen Cook publicado em 1971,(tamb\xc3\xa9m chamado teorema de Cook-Levin), para mostrar que existe uma redu\xc3\xa7\xc3\xa3o por mapeamento em tempo polinomial do problema de satisfatibilidade para cada uma das 21 dos problemas computacionais de combinat\xc3\xb3ria\xc2\xa0e da\xc2\xa0teoria dos grafos, mostrando assim que todos eles s\xc3\xa3o NP-completos. Esta foi uma das primeiras demonstra\xc3\xa7\xc3\xb5es de que muitos problemas computacionais naturais que ocorrem ao longo da ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o s\xc3\xa3o computacionalmente intrat\xc3\xa1veis, e aumentou o interesse no estudo da NP-completude e do problema "P vs NP".'