NP-difícil: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 13:
* Uma vez que os problemas NP-completos transformam-se uns aos outros por [[Transformação polinomial|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.
▲<!--
A common mistake is to think that the ''NP'' in ''NP-hard'' stands for ''non-polynomial''. Although it is widely suspected that there are no polynomial-time algorithms for NP-hard problems, this has never been proven. Moreover, the class [[NP (complexity)|NP]] also contains all problems which can be solved in polynomial time.
| |||