TSP vs. Word Unscrambler

Question

Будет ли проблема выдавать, является ли данное скремблированное слово истинным английским словом, является эквивалентной проблемой для проблемы коммивояжера? Хорошо известная стратегия состоит в том, чтобы сгенерировать все перестановки данного слова и сравнить все их со всеми словами в английском словаре. Этот алгоритм будет иметь временную сложность O(N!). Я мог представить себе, что эти два отличаются в важном аспекте: если вы найдете перестановку, которая соответствует слову, вы можете прекратить генерировать перестановки, тогда как с помощью TSP вам придется проверять каждую комбинацию маршрутов независимо. Однако я написал алгоритм, который вместо генерации всех перестановок заданного слова длиной n вместо этого сортирует буквы в данном слове и выполняет тот же алгоритм на словах словаря, а затем сравнивает две отсортированные строки (этот метод работает в 100% случаев). Мой алгоритм использует сортировку по умолчанию Java, и после исследования я обнаружил, что он работает от O(n log n). В целом, моя программа работает от O(n log n), потому что этот термин растет самым большим, поскольку n приближается к бесконечности. Этот алгоритм работает меньше, чем полиномиальное время. Итак, если проблемы эквивалентны, не могли бы вы использовать аналогичный метод для решения проблемы TSP? Как это относится к P против NP? Извините, если что-либо из этого не имеет смысла, или я не использовал терминологию правильно, я не так разбираюсь в этом поле

Answer 1

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

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

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