Что делает «если P1 уменьшается до P2, то P2 по крайней мере так же сложно, как P1» означает?

Question

У меня проблемы с пониманием следующего утверждения в отношении снижения Turging:

"Если P1 уменьшается до P2, то P2 по крайней мере так же сложно, как P1."

Это означает, что

(i) p2 может быть сложнее или так же сложно, как P1, или (ii) P2 может быть проще или так же сложно, как P1?

Чтобы представлять это визуально ...

Я был бы признателен за любые понимание по этому вопросу.Спасибо.

Answer 1

Интерпретация (i) верна: « $ A $ по крайней мере так же сложно, как $ B $ «означает, что $ a $ так же сложно, как или строго сложнее, чем $ B $ .(Подумайте о числах: « $ a $ , по крайней мере, такой же большой, как $ B $ " означает " $ a= b $ или $ a> b $

.

Обратите внимание, что не только « $ a $ по крайней мере так же сложно, как $ B $ "исключить $ a $ строго слабее, чем $ B $ , он также правит $ a $ и $ b $ Быть из несравненная сложность .Сложность не линейный порядок;Мы можем найти такие проблемы, которые не помогают нам решить другой.