O que "se P1 for reduzido para P2, então P2 é pelo menos tão duro quanto p1"?

Question

Estou tendo problemas para entender a seguinte declaração sobre a redução de Turing:

.

"Se P1 for reduzido para P2, o P2 é pelo menos tão duro quanto p1."

Isso significa que

(i) p2 pode ser mais difícil ou tão duro quanto p1, ou (ii) P2 pode ser mais fácil ou tão duro quanto P1?

Para representar isso visualmente ...

Eu apreciaria qualquer insight sobre o assunto.Obrigado.

Answer 1

interpretação (i) está correta: " $ a $ é pelo menos tão duro quanto $ B $ "significa que a $ a $ é tão difícil quanto ou estritamente mais difícil do que $ B $ .(Pense em números: " $ a $ é pelo menos tão grande quanto $ B $ " significa " $ a= b $ ou $ a> b $ . ")

.")

. ")

")

Observe que não só " $ a $ é pelo menos tão duro quanto $ B $ "descarte $ a $ ser estritamente mais fraco do que $ B $ , também exclui $ a $ e $ b $ ser de complexidade incomparável .A complexidade não é uma ordem linear;Podemos encontrar problemas de modo que nem nos ajuda a resolver o outro.