Embora ainda não se conheçam algoritmos eficientes para resolvê-los, problemas NP-difíceis estão, com frequência, presentes em situações reais que demandam soluções rápidas, justificando o interesse por métodos não exatos como heurísticas e algoritmos aproximativos.