NP-difícil
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 se e somente se (sse) existe um problema NP-completo L que é Turing-redutível em tempo polinomial para H (i.e., L?=?TH). Em outras palavras, "L" pode ser resolvido em tempo polinomial por uma Máquina de Turing não determinística com um oráculo para "H". Informalmente, podemos pensar em um algoritmo que pode chamar tal Máquina de Turing Não-Determinística 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: problemas de decisão, problemas de pesquisa ou problemas de otimização.

Como conseqüências da definição, temos que (note que estas afirmações não são definições):
* O problema "H" é pelo menos tão difícil quanto L, porque H pode ser usado para resolver "L";
* Como "L" é NP-completo e, portanto, o mais difícil na classe NP, também o problema "H" é pelo menos tão difícil quanto um NP, mas "H" não tem que estar em NP e, consequentemente, não tem de ser um problema de decisão (mesmo que seja um problema de decisão, ele não precisa estar em NP);
* Uma vez que os problemas NP-completos transformam-se uns aos outros por redução um-para-muitos em tempo polinomial (também chamada de transformação polinomial), todos os problemas NP-completos podem ser resolvidos em tempo polinomial por uma redução para "H", Assim, todos os problemas em NP reduzem para "H"; note-se, porém, que isso envolve a combinação de duas transformações diferentes: de problemas de decisão NP-completos para o problema NP-completo "L" por transformação polinomial, e de "L" para "H" pela redução em tempo polinomial de Turing;
* Se existe um algoritmo polinomial para qualquer problema NP-difícil, então existem algoritmos polinomiais para todos os problemas em NP, e, portanto, P = NP;
* Se P != NP, então os problemas NP-difíceis não têm soluções em tempo polinomial, uma vez que P = NP não resolve se os problemas NP-difíceis podem ser resolvidos em tempo polinomial;
* Se um problema de otimização H tem uma versão de decisão NP-completo "L", então "H" é NP-difícil.

Um erro comum é pensar que "NP" em "NP-difícil" representa "não-polinomial". Embora seja amplamente suspeito de que não existem algoritmos de tempo polinomial para problemas NP-difíceis, isto nunca foi provado. Além disso, a classe NP contém também todos os problemas que podem ser resolvidos em tempo polinomial.
Q5157286
teoria da complexidade computacional
Concept
Q949972
sse
Concept
Q215206
NP-completo
MISC
None
Turing-redutível em tempo polinomial
UNK
None
tempo polinomial
UNK
Q1190223
Máquina de Turing não determinística
Concept
Q3262192
problemas de decisão
Concept
Q2362762
problemas de pesquisa
Concept
Q984063
problemas de otimização
Concept
None
redução um-para-muitos em tempo polinomial
UNK
Q628036
NP
MISC
Q1137554
NP-difícil
MISC
Q1137554
NP-difícil
MISC
Q1137554
NP-difícil
MISC
Q1137554
NP-difícil
MISC
Q1137554
NP-difícil
MISC
part of