Dureza NP
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.
Perguntas e Respostas
P: O que é um problema NP-difícil?
R: Um problema NP-difícil é um tipo de problema matemático usado na ciência da computação que é um problema do tipo sim/não em que encontrar uma solução para ele é pelo menos tão difícil quanto encontrar uma solução para o problema mais difícil cuja solução possa ser rapidamente verificada como verdadeira.
P: É possível verificar rapidamente uma solução funcional para todos os problemas NP-difíceis?
R: Não, apenas alguns problemas NP-difíceis, chamados de problemas NP, têm soluções que podem ser verificadas rapidamente.
P: Como é chamada a categoria de problemas NP-difíceis que também são problemas NP?
R: Os problemas NP-difíceis que também são problemas NP se enquadram em uma categoria chamada NP-completo.
P: Todos os problemas NP-difíceis são NP-completos?
R: Não, nem todos os problemas NP-difíceis são NP-completos. Somente aqueles que também são problemas NP se enquadram nessa categoria.
P: Os problemas NP-difíceis são fáceis de resolver?
R: Não, os problemas NP-difíceis não são fáceis de resolver. Na verdade, encontrar uma solução para eles é, no mínimo, tão difícil quanto encontrar uma solução para o problema mais difícil cuja solução possa ser rapidamente verificada como verdadeira.
P: Há alguma vantagem em resolver problemas NP-difíceis?
R: Sim, a solução de problemas NP-difíceis pode oferecer vantagens em vários campos, como ciência da computação, física e ciências sociais, pois eles podem exigir cálculos e modelagem complexos.
P: Há pesquisas em andamento para resolver problemas NP-difíceis?
R: Sim, a pesquisa para resolver problemas NP-difíceis está em andamento, pois esses problemas continuam a ser relevantes em vários campos, e encontrar algoritmos e soluções eficientes pode ter implicações significativas.
