Qu'est-ce que "si p1 est réduit à P2, P2 est au moins aussi difficile que P1"?

Question

J'ai du mal à comprendre la déclaration suivante concernant la réduction Turing:

"Si P1 est réduit à P2, P2 est au moins aussi acharné que P1."

Cela signifie-t-il que

(i) p2 peut être plus difficile ou aussi dur que P1, ou (ii) P2 peut être plus facile ou aussi difficile que P1?

Pour représenter cela visuellement ...

J'apprécierais tout aperçu de la question.Merci.

Answer 1

interprétation (i) est correct: " $ a $ est au moins aussi difficile que $ B $ "signifie que $ a $ est aussi dur que ou strictement plus difficile que $ B $ .(Pensez à des chiffres: " $ a $ est au moins aussi gros que $ b $ " signifie " $ A= B $ ou A> B $ . ")

"

Notez que non seulement " $ a $ est au moins aussi difficile que $ B $ "exclure $ a $ être strictement plus faible que $ B $ , il exclut également $ A $ et $ B $ être de complexité incomparable .La complexité n'est pas une commande linéaire;Nous pouvons trouver des problèmes tels que ni nous ne nous aide pas à résoudre l'autre.