¿Qué hace "Si P1 se reduce a P2, entonces P2 es al menos tan difícil como P1"?

Question

Tengo problemas para comprender la siguiente declaración sobre la reducción de Turing:

"Si P1 se reduce a P2, entonces P2 es al menos tan difícil como P1".

¿Esto significa que

(i) P2 puede ser más difícil o tan duro como P1, o (ii) P2 puede ser más fácil o tan duro como P1?

para representar esto visualmente ...

Agradecería cualquier información sobre el asunto.Gracias.

Answer 1

Interpretación (I) es correcta: " $ a $ es al menos tan duro como $ b $ "significa que $ A $ es tan difícil o estrictamente más difícil que $ b $ .(Piense en números: " $ a $ es al menos tan grande como $ b $ " significa " $ A= B $ o $ a> b $ . ")

Nota que no solo " $ a $ es al menos tan duro como $ b $ "Descarga fuera $ a $ siendo estrictamente más débil que $ b $ , también descarta $ a $ y $ b $ siendo de complejidad incomparable .La complejidad no es un orden lineal;Podemos encontrar problemas como que ninguno nos ayuda a resolver el otro.