Lembra-se do que é um problema NP-completo? Como ele difere de simplesmente NP?

NP (tempo polinomial não determinístico) é uma classe de problemas para os quais a solução pode ser verificada em tempo polinomial. Ou seja, se você tem um candidato à resposta, pode verificar rapidamente se está correto ou não.

Problemas NP-completos são um subconjunto de NP que são ao mesmo tempo os mais "difíceis" nesta classe. Se alguém encontrasse um algoritmo polinomial para resolver qualquer problema NP-completo, então todos os problemas em NP poderiam ser resolvidos em tempo polinomial.

Diferença principal:

• NP: problemas cujas soluções podem ser verificadas rapidamente.
• NP-completo: problemas em NP aos quais qualquer outro problema NP pode ser reduzido (ou seja, são os "mais difíceis" em NP).

Exemplo: o problema do clique de tamanho máximo em um grafo é NP-completo, e o problema de verificar se um subconjunto de elementos soma a um número dado está em NP.