Sumários

21 Fevereiro 2025, 13:30 • Pedro Martins Pereira Serrão de Moura

Motivação.

Noção de transformação polinomial entre dois problemas. Exemplos

Problema de decisão associado a um problema de otimização.

As classes P, NP, NP-complete. Problemas NP-difícil.

Alguns problemas NP-Hard: discussão e obtenção de soluções admissíveis.