Мне интересно, является ли TSP-OPTIMIZE NP-эквивалентным, как proof wiki, заявляет , или это строго NP-hard.Чтобы уточнить, я говорю о проблеме оптимизации, которая заключается в том, чтобы найти кратчайший путь туда и обратно для данного графика.Редактировать: Насколько я могу следить за тем, как доказательство пытается показать его для экземпляров TSP с целыми весами ребер, очевиден вопрос, является ли это расширяемым на R, оно может быть расширено на все, что может быть выражено численно.Он решает задачу оптимизации, вычисляя сначала минимальный вес с помощью бинарного поиска, а затем вычисляет кратчайший путь туда и обратно с суммами (n, ..., 1) в O (n ^ 2) вычислениях решения задачи.Поэтому сводим его полиномиально к решению проблемы.Решение проблемы, очевидно, можно решить за полиномиальное время с помощью оракула.Доказательства не содержат хороших цитат, хотя, и я задаюсь вопросом, знает ли кто-нибудь хорошие цитаты относительно проблемы оптимизации.Если у вас есть несколько хороших ссылок на евклидову TSP-OPTIMIZE, это было бы здорово!
Любая помощь приветствуется.
Кстати: что касается NP-жесткого и NP-эквивалента, я знаю, что терминология в этой области все еще немного грубая, и некоторые считают термины недействительными для задач оптимизациино я собираюсь с эквивалентными терминами Википедия .Термины важны, но, пожалуйста, не оставляйте вопрос в стороне, потому что он не подходит для какого-то конкретного термина для класса задачи.