Почему A _ <B всегда верно в полиномиальной редукции?

Question

Я очень хорошо знаком с компьютерными науками, особенно с теоретической стороны, поэтому я пытаюсь понять (без ответа слишком далеко за моей головой), почему всегда верно для сокращения полиномиального времени, и является ли мой наивный теория о том, почему объясняет это (что я подозреваю, не делает).

Моя идея:

Предпосылка: Начиная, у меня есть две проблемы A и B, где я либо нахожу гораздо более вычислительно затратные по времени вычисления, чем B с использованием алгоритма для ИИ, либо у меня нет у меня вообще есть алгоритм для A (что делает его действительно очень сложным - хотя я надеюсь, что я правильно использовал этот термин здесь)? Хотя я понимаю, что могу преобразовать А в В и сделать именно это.

Когда кто-то говорит, что после такого сокращения решение A всегда самое трудное, как решение для B, это не означает, что любой алгоритм, который решает A, самое большее, как B, но на самом деле строго, что самое эффективное из известных на данный момент решение, которое мы будем иметь для A отныне (которое, конечно, может быть изменено, когда мы находим все более и более эффективные алгоритмы для проблемы) будет максимум, так же сложно, как B или проще?

Почему : просто 3 случая - во-первых, если A было очень трудно решить с помощью моего алгоритма, но B было легче решить, и я использовал B, чтобы решить A, ну, теперь мое самое эффективное решение A - это алгоритм для B. Во-вторых, если у меня вообще не было решения для A, но я сократил A до B, то теперь у меня есть 1 решение для A, поэтому «объединение всех моих решений» так же сложно, как и от B. В-третьих, скажем, мое лучшее решение для A всегда было проще, чем B, но я «свел» его к B для забавы, ну, мое лучшее решение действительно проще, чем B.

Может быть бесконечно больше решений A, которые сложнее, чем B (например, алгоритм, который решает 2 + x = 4 сразу, по сравнению с алгоритмом, который делает то же самое, но по какой-то причине добавляет 1 миллион раз к уравнению , прежде чем вычесть это снова, затем решить).

Критически: Итак, с тех пор существует множество способов решения проблемы А, которые являются произвольно более сложными, чем любое конкретное решение, имеет смысл говорить о только с точки зрения наиболее эффективных решений для каждого , которые известны в настоящее время .

Это правильно?

Большое спасибо за вашу помощь, я действительно ценю это.

Answer 1

Вообще говоря, когда люди обсуждают «проблемы» и «как трудно их решить», они имеют в виду класс проблем (например, проблему коммивояжера), а не конкретный случай проблемы (например, путешествие проблема продавца с городами A, B, C ... и расстояниями X, Y, Z, ...). Кроме того, когда они обсуждают, насколько трудной / легкой является проблема, они обращаются к наиболее эффективному из возможных решений. Не очень интересно говорить о том, как трудно решить проблему, используя случайное решение (которое может быть действительно неэффективным), поэтому часто решения сопровождаются доказательствами того, что не может быть более эффективного решения.

Таким образом, если класс проблемы A можно преобразовать в класс проблемы B, то вы знаете, что существует решение A, которое по крайней мере так же эффективно, как B, поскольку одно из решений состоит в том, чтобы преобразовать его в B и решить это таким образом. Это может быть более эффективным, поскольку может существовать решение, уникальное для проблем типа A, которое более эффективно, чем проблемы типа B, но оно будет, по крайней мере, таким же эффективным, как B.

Таким образом, ваше мышление направлено в правильном направлении, но меньше сосредотачивается на «решениях, о которых вы знаете», а больше на теоретически наиболее эффективном решении проблемы.