21 problemas NP-completos de Karp
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".
Os problemas editar
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)
- 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)
- Chromatic number (também chamado do problema de coloração de grafos)
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.[3] 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).
Veja também editar
- Lista dos problemas NP-completo (em inglês)
Referências
- ↑ 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
- ↑ Zuckerman, David (dezembro de 1996). «On Unapproximable Versions of NP-Complete Problems». SIAM Journal on Computing (em inglês) (6): 1293–1304. ISSN 0097-5397. doi:10.1137/S0097539794266407. Consultado em 29 de outubro de 2023