Um problema NP duro é um problema de sim/não onde encontrar uma solução para ele é pelo menos tão difícil quanto encontrar uma solução para o problema mais duro cuja solução pode ser rapidamente verificada como sendo verdadeira. Alguns problemas NP-duros são aqueles em que uma solução de trabalho pode ser verificada rapidamente (problemas NP) e alguns não são. Os problemas NP-duros que também são problemas NP enquadram-se em uma categoria chamada NP-completo.
Um exemplo de um problema que é pelo menos tão difícil de resolver quanto qualquer outro problema para o qual podemos verificar rapidamente as soluções, o que também é rapidamente verificável (é tanto NP-duro como NP):
Um vendedor ambulante quer visitar 100 cidades dirigindo, começando e terminando sua viagem em casa. Ele tem um suprimento limitado de gasolina, de modo que ele só pode dirigir um total de 10.000 quilômetros. Ele quer saber se ele pode visitar todas as cidades sem ficar sem gasolina.
As pessoas não sabem como resolver este problema mais rápido do que testar cada resposta possível, mas se for encontrada uma solução que permita ao vendedor fazer isto, podemos usar um algoritmo de verificação de que isto é verdade. Este problema também é conhecido como problema do Vendedor Viajante.
Um exemplo de um problema que é pelo menos tão difícil de resolver quanto qualquer outro problema que podemos verificar rapidamente as soluções, mas que não pode ser verificado rapidamente (é NP-difícil, mas não é NP):
se alguém inicia um programa que simplesmente vai,
enquanto(true){ continuar; }e nunca a pára, será que ela funcionará para sempre?
Não há uma maneira conhecida de encontrar uma solução para todos os problemas deste tipo, e isto também não pode ser verificado.