Revisão das 20h57min de 30 de junho de 2010 editar Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 510 edições ← Ver a alteração anterior		Revisão das 00h22min de 1 de julho de 2010 editar desfazer Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 510 edições Ver a alteração posterior →
Linha 3: [[Ficheiro:P np np-completo np-hard.svg\|thumb\|300px\|right\|[[Diagrama de Euler]] para o conjunto de problemas [[P (complexidade)\|P]], [[NP (complexidade)\|NP]], [[NP-completo]], e NP-hard]] '''NP-difícil''' (ou '''NP-hard''', ou '''NP-complexo''') na [[teoria da complexidade computacional]], é uma classe de problemas que são, informalmente, "Pelo menos tão difíceis quanto os problemas mais difíceis em NP". Um problema ''H'' é NP-difícil [[sse]] existe um problema [[NP-completo]] L que é [[Redução em tempo polinomial de Turing\|Turing-redutível em tempo polinomial]] para H (i.e., L ≤ <sub>T</sub>H). Em outras palavras, ''L'' pode ser resolvido em [[tempo polinomial]] por uma [[Máquina Oracle\|máquina oracle]] com um oracle para ''H''. Informalmente, podemos pensar em um algoritmo que pode chamar tal máquina oracle como uma sub-rotina para resolver ''H'', e resolver ''L'' em tempo polinomial, se a chamada da sub-rotina leva apenas um passo para computar. Problemas NP-difíceis podem ser de qualquer tipo: [[Problema de decisão\|problemas de decisão]], [[Problema de busca\|problemas de pesquisa]] ou [[Problema de otimização\|problemas de otimização]]. <!-- {{for\|a gentler introduction\|P versus NP problem}} ...A problem ''H'' is NP-hard [[if and only if]] there is an [[NP-complete]] problem L that is [[polynomial-time Turing reduction\|polynomial time Turing-reducible]] to H (i.e., L ≤ <sub>T</sub>H). In other words, ''L'' can be solved in [[polynomial time]] by an [[oracle machine]] with an oracle for ''H''. Informally, we can think of an algorithm that can call such an oracle machine as a subroutine for solving ''H'', and solves ''L'' in polynomial time, if the subroutine call takes only one step to compute. NP-hard problems may be of any type: [[decision problem]]s, [[search problem]]s, or [[optimization problem]]s. As consequences of definition, we have (note that these are claims, not definitions):

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