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