Что делает «если P1 уменьшается до P2, то P2 по крайней мере так же сложно, как P1» означает?
-
29-09-2020 - |
Вопрос
У меня проблемы с пониманием следующего утверждения в отношении снижения Turging:
"Если P1 уменьшается до P2, то P2 по крайней мере так же сложно, как P1."
Это означает, что
(i) p2 может быть сложнее или так же сложно, как P1, или (ii) P2 может быть проще или так же сложно, как P1?
Чтобы представлять это визуально ...
Я был бы признателен за любые понимание по этому вопросу.Спасибо.
Решение
Интерпретация (i) верна: « $ A $ по крайней мере так же сложно, как $ B $ «означает, что $ a $ так же сложно, как или строго сложнее, чем $ B $ .(Подумайте о числах: « $ a $ , по крайней мере, такой же большой, как $ B $ " означает "
Обратите внимание, что не только « $ a $ по крайней мере так же сложно, как $ B $ "исключить $ a $ строго слабее, чем $ B $ , он также правит $ a $ и $ b $ Быть из несравненная сложность .Сложность не линейный порядок;Мы можем найти такие проблемы, которые не помогают нам решить другой.