Полиномиальное сокращение времени от A до B - B по крайней мере так же сложно, как A

Question

Много раз я слышал, что если мы сможем уменьшить задачу A до задачи B в полиномиальное время, то проблема B по крайней мере такая же сложная задача А. Насколько точно это утверждение? Я считаю, что мы должны понимать это следующим образом: если A может быть сведено к многократному времени до B, то, если для B существует алгоритм с многократным временем, то он должен быть там для A.

Мою точку в том, что A может на самом деле будет сложнее B (может иметь более высокую временную сложность, например O (n^100), по сравнению с B-O (n^4), поскольку сама по себе временная регрессия может занять много времени. Таким образом, сумма O (n^4), а время, необходимое для редукции, может дать алгоритм для A, который будет O (n^100). Поэтому каждый раз, когда я читаю A, в этом контексте не сложнее B, так это то, что A не может иметь никакого полиномиального времени алгоритм в то время как B имеет один. правильно ли это?

Answer 1

Correct.

В общем, сказал бы, что термин «жесткий» в этом утверждении соответствует complexity class, а не до степени полинома. Или, скорее, «жесткость» проблемы - это минимальный класс сложности, содержащий эту проблему.

То есть, если А по крайней мере так сложно, как B, то минимальный класс сложности для B заменяется минимальной сложности класса А.

Answer 2

Как @Inspired указывает, что это утверждение родственный к классу сложности, а не по фактической временной сложности двух проблем, это утверждение обычно используется для NP-задач.