NP-difícil: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Página marcada como sem fontes, usando FastButtons |
Adicionado o link para a soma de subconjuntos |
||
Linha 17:
== Exemplos ==
Um exemplo de um problema NP-difícil é o problema de decisão [[Problema da soma
Há também problemas de decisão que são NP-difíceis, mas não NP-completos, por exemplo, o [[problema da parada]]. Este é o problema que pergunta se "dado um programa e dada a sua entrada, ele irá executar para sempre?" Esta é uma questão do tipo ''sim''/''não'', por isso este é um problema de decisão. É fácil provar que o problema da parada é ''NP-difícil'', mas não ''NP-completo''. Por exemplo, o [[problema de satisfatibilidade booleana]] pode ser reduzido ao problema da parada, transformando-o em uma descrição de uma [[máquina de Turing]] que tenta todos as atribuições verdadeiras e quando encontra uma que satisfaça a fórmula, ela para, caso contrário, entra em um loop infinito. Também é fácil ver que o problema da parada não está na classe ''NP'' já que todos os problemas em NP são decidíveis em um número finito de operações, enquanto o problema da parada, em geral, não é. Há também problemas NP-difíceis que não são NP-completos nem indecidíveis.
| |||