Was macht "Wenn P1 auf P2 reduziert ist, dann ist P2 zumindest so hart wie P1"?

Question

Ich habe Probleme, die folgende Erklärung zur Turing-Reduktion zu verstehen:

"Wenn P1 auf P2 reduziert ist, dann ist P2 mindestens so hart wie P1."

bedeutet das, dass

(i) p2 kann schwieriger oder so hart wie P1 sein oder (ii) p2 kann einfacher oder so hart wie P1 sein?

um dies visuell darzustellen ...

Ich würde den Einblick in die Angelegenheit freuen.Danke.

Answer 1

Interpretation (I) ist korrekt: " $ A $ ist mindestens so hart wie der $ B $ "Bedeutet, dass $ A $ so hart wie oder streng härter ist als $ B $ .(Denken Sie an Zahlen: " $ A $ ist mindestens so groß wie $ B $ " bedeutet " $ A= B $ oder $ A> B $ . ")

Beachten Sie, dass nicht nur " $ A $ mindestens so hart wie $ B $ " ist "Regel raus $ A $ Streng schwächer als $ B $ , es regiert auch $ A $ und $ B $ von unvergleichlicher Komplexität .Komplexität ist keine lineare Ordnung;Wir können solche Probleme finden, das uns weder hilft, das andere zu lösen.