Revisão das 23h59min de 2 de julho de 2010 editar Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 841 edições →‎Exemplos ← Ver a alteração anterior		Revisão das 17h34min de 3 de julho de 2010 editar desfazer Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 841 edições Ver a alteração posterior →
Linha 25: Um exemplo de um problema NP-difícil é o problema de decisão [[Problema 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 caixeiro viajante]]. 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''. <!--▼ ▲<!-- ~~There are also decision problems that are NP-hard but not NP-complete, for example the [[halting problem]]~~. ~~This is the problem which asks "given a program and its input, will it run forever?" That's a ''yes''/''no'' question, so this is a decision problem~~. ~~It is easy to prove that the halting problem is ''NP-hard'' but not ''NP-complete''~~. For example, the [[Boolean satisfiability problem]] can be reduced to the halting problem by transforming it to the description of a [[Turing machine]] that tries all [[truth value]] assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in ''NP'' since all problems in NP are decidable in a finite number of operations, while the halting problem, in general, is not. There are also NP-hard problems that are neither NP-complete nor [[Recursive language\|undecidable]]. For instance, the language of [[True quantified Boolean formula]]s is decidable in [[PSPACE\|polynomial space]], but not non-deterministic polynomial time (unless NP = [[PSPACE]]). == Alternative definitions ==

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