NP-difícil: diferenças entre revisões

Um exemplo de um problema NP-difícil é o problema de decisão [[problemaProblema da soma de subconjuntos|da soma de subconjuntos]], que é o seguinte: dado um conjunto de números inteiros, pode algum subconjunto não-vazio deste somar zero? Isso é uma questão do tipo ''sim''/''não'', e acontece de ser NP-completo. Outro exemplo de um problema NP-difícil é o problema de otimização de se encontrar a rota de menor custo através de todos os nós de um grafo ponderado. Isto é comumente conhecido como o [[Problema do Caixeirocaixeiro Viajanteviajante]].