Если X ≤p Y, может ли Y ≤p X?

Question

Я думаю, что ответ - нет, но у меня возникли проблемы с пониманием проблемы.В непрофессионале, по сути, спрашивается, что если проблема x может быть сведена к проблеме y за полиномиальное время, то y также может быть уменьшена до x за полиномиальное время, верно?И из того, как оно написано с использованием неравенств, оно должно быть ложным.

Если X ≤p Y в непрофессионале, это говорит о том, что X можно уменьшить за полиномиальное время до Y

Тогда возникает вопрос:≤p X, который в непрофессионале предлагает уменьшить y за полиномиальное время до X

Эта проблема меня просто немного смущает.

Answer 1

Я думаю, вы хотите спросить: «Означает ли X ≤p Y, что Y ≤p X?».

Ответ - нет.Например, 2-SAT может быть легко уменьшен до 3-SAT, но 3-SAT не может быть уменьшен до 2-SAT за время P, если P = NP.

Если P = NP, ответ по-прежнемунет.Например, любая проблема решения P-времени может быть сведена к проблеме остановки, но проблема остановки неразрешима.

Answer 2

Ответ:

Итак, мы имеем X ≤p Y.Вы спрашиваете, возможно ли, что также Y ≤p X?

Хорошо подумайте: а что если X и Y - это одна и та же проблема?Затем, тривиально, X может быть сведен к себе за полиномиальное время (просто пройдя исходный экземпляр задачи), поэтому мы имеем X ≤p Y.Но тогда из того же аргумента следует, что Y ≤p X!

Таким образом, мы нашли такой пример, что X ≤p Y и Y ≤p X, поэтому ответ на ваш вопрос - да.

(Однако, конечно, не верно, что ЛЮБЫЕ проблемы X и Y могут быть уменьшены обоими способами за полиномиальное время.)

Аналогия с целыми числами:

Как вы, похоже, указываете и в своем вопросе, определенно есть некоторые сходства между ≤p и нормальным неравенством ≤, например, между целыми числами: Скажите a ≤ b.Может ли тогда быть правдой, что b ≤ a?Ну да!Всякий раз, когда a = b.

В контексте вычислительных задач две задачи X и Y не обязательно должны быть идентичными, чтобы их можно было сводить в обоих направлениях.(Всегда легко найти две проблемы, которые идентичны, но для какой-то произвольной детализации.)

Например (на несколько более высоком уровне), проблема нахождения наибольшего значения 1038 * вМассив целых чисел может быть легко сведен к проблеме поиска наименьшего (просто отрицая все элементы).Затем, тривиально, мы также можем уменьшить проблему нахождения наименьшего целого числа до задачи нахождения наибольшего (просто отрицая снова).