Линейно-временное уменьшение симметрично?

Question

Если проблема X сводится к задаче Y, то также возможна и противоположная редукция? Скажет

X = Дан массив сказать, если все элементы различны

Y = Отсортировать массив, используя сравнение сортировки

Теперь X сводится к Y в линейное время, т.е. если я могу решить Y, я могу решить X в линейном времени. Всегда ли верно обратное? Могу ли я решить Y, учитывая, что я могу решить X? Если да, то как?

Под редукцией я имею в виду следующее:

Problem X linear reduces to problem Y if X can be solved with: 
a) Linear number of standard computational steps. 
b) Constant calls to subroutine for Y. 

Answer 1

Предполагая, что я понимаю, что вы имеете в виду сокращения, скажем, что у меня есть проблема, которую я могу решить в O(N) используя массив пар ключ/значение, что это проблема поиска чего-то из списка. Я могу решить ту же проблему в O(1) с помощью Словаря.

Означает ли это, что я могу вернуться к своей первой технике и использовать ее для решения одной и той же проблемы в O(1)?

Я так не считаю.

Answer 2

Предположим, что я могу решить задачу A в постоянное время O (1), но задача B имеет наилучшее экспоненциальное решение времени O (2^n). Вероятно, я могу придумать безумно сложный способ решения задачи A в O (2^n) («сокращение» проблемы A до B), но если ответ на ваш вопрос был «ДА», тогда я должен был бы быть в состоянии сделать все чрезвычайно трудные задачи разрешимыми в O (1). Конечно, этого не может быть!

Answer 3

Учитывая приведенный выше пример:

Вы можете определить, если все элементы различны в O(N), если подкреплять их хэш-таблицу. Это позволяет проверить существование в O(1) + накладные расходы хэш-функции (что обычно не имеет значения). Если вы делаете что-то вроде не на основе сравнения:

sorting algorithm list

Specialized sort that is linear:

Для простоты предположим, что вы рассортировать список натуральных чисел. Метод сортировки проиллюстрирован с использованием сырых стержней спагетти: Для каждого числа x в списке получите стержень длины x. (Один из практических способов выбора устройства - позволить самому большому числу m в вашем списке соответствовать одному полному стержню спагетти. В этом случае полный стержень равен m спагетти. Чтобы получить стержень длиной x, просто сложите стержень в два, чтобы одна часть имела длину х единиц, отбросьте другую часть.)

Как только у вас есть все ваши палочки для спагетти, возьмите их свободно в кулак и опустите их к столу, чтобы все стояли вертикально, опираясь на поверхность стола. Теперь, для каждого стержня, опустите другую руку сверху, пока она не встретится со стержнем - это, безусловно, самое длинное! Удалите этот стержень и вставьте его в переднюю часть (первоначально пустой) выходного списка (или, что то же самое, поместите его в последний неиспользуемый слот выходного массива). Повторяйте до тех пор, пока все стержни не будут удалены.

Так что, если вы зададите очень специализированный случай вашей проблемы, ваше утверждение будет выполнено. Однако это не будет в общем случае, что, похоже, больше того, что вам нужно. Это очень похоже на то, когда люди думают, что они решили TSP, но вместо этого создали ограниченную версию общей проблемы, которая разрешима с использованием специального алгоритма.