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

* O problema ''H'' é pelo menos tão difícil quanto L, porque H pode ser usado para resolver ''L'';

 

 

* 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;