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", Richard Karp usou o teorema de que o problema da satisfatibilidade é NP-completo 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".
Os problemas Os 21 problemas de Karp são mostrados abaixo, muitos com seus nomes originais. O aninhamento indica a direção das reduções utilizado. Por exemplo, knapsack foi mostrado como sendo NP-completo, reduzindo exact cover para o knapsack.
Satisfiability: o problema de satisfatibilidade booleana para fórmulas na forma normal conjuntiva (muitas vezes referido como SAT) 0–1 integer programming (A variação em que apenas as restrições devem ser satisfeitas, sem otimização) Clique (veja também o problema do conjunto independente) Set packing Vertex cover Set covering Feedback node set Feedback arc set Directed Hamilton circuit Undirected Hamilton circuit Satisfiability with at most 3 literals per clause (equivalente a 3-SAT) Chromatic number (também chamado do problema de coloração de grafos) Clique cover Exact cover Hitting set Steiner tree 3-dimensional matching Knapsack (A definição de Karp sobre Knapsack é mais próxima do problema da soma dos subconjuntos) Job sequencing Partition Max cut
Com o passar do tempo descobriu-se que muitos dos problemas podem ser resolvidos de forma eficiente, se restrito a casos especiais, ou pode ser resolvido dentro de qualquer um percentual fixo do resultado ideal. No entanto, David Zuckerman mostrou, em 1996, que cada um destes 21 problemas tem uma versão de otimização restrita que é impossível aproximar dentro de qualquer fator constante, a menos que P = NP, mostrando que a abordagem da redução de Karp generaliza para um tipo específico de redução por aproximabilidade. No entanto, estas podem ser diferentes do padrão de otimização das versões dos problemas, e podem ter aproximação algorítmica (como no caso de maximum cut).
Categoria:Listas de matemática