Cosa significa "Se P1 è ridotto a P2, P2 è almeno tanto dura come P1"?

Question

Ho difficoltà a capire la seguente dichiarazione in merito alla riduzione del Turing:

.

"Se P1 è ridotto a P2, P2 è almeno tanto dura come P1."

significa questo

(i) P2 può essere più difficile o difficile come P1, o (ii) P2 può essere più facile o difficile come P1?

Per rappresentare questo visivamente ...

apprezzerei qualsiasi intuizione sulla questione.Grazie.

Answer 1

Interpretazione (i) è corretto: " $ A $ è almeno come $ B $ "significa che $ A $ è difficile come o rigorosamente più difficile di $ B $ .(Pensa ai numeri: " $ A $ è almeno grande come $ B $ " significa " $ A= B $ o $ A> B $ . ")

Nota che non solo " $ A $ è almeno come $ B $ "escludere $ A $ essendo strettamente più debole di $ B $ , regola anche $ A $ e $ B $ essere di complessità incomparabile .La complessità non è un ordine lineare;Possiamo trovare problemi che non ci aiuta a risolvere l'altro.