TSP и P vs NP

[Soul Friend]

Задача коммивояжера, TSP, относится к NP полным задачам. Если найти для него алгоритм который решает эту задачу за полиномиальное время то будет ли это означать что $P=NP$ или просто выведут задачу TSP из под NP, а P vs NP останется открытой ?

[vpb]

Soul Friend в сообщении #1676073 писал(а):

то будет ли это означать

Да, будет. Попался как-то текст некоего человека с Урала, Панюков фамилия, который якобы так и сделал. Глянул --- белиберда.

[Dmitriy40]

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

[vpb]

В известном списке "проблем для сумасшедших" (см., например, "Правила для авторов" "Известий РАН, серия математическая" на портале mathnet.ru ) равенство классов P и NP (проблема Кука) занимает почетное второе место, а первое принадлежит гипотезе Римана.

[Null]

Dmitriy40 в сообщении #1676085 писал(а):

все задачи из класса NP сводятся одна к другой

Я читал что это верно для задач NP-complete. Я что-то не так понял?

[Dmitriy40]

Null
Нет, тогда скорее это я что-то недопонял.

[Sender]

Null в сообщении #1676127 писал(а):

Я читал что это верно для задач NP-complete. Я что-то не так понял?

Класс NP-полных задач (NPC) содержится в NP, неизвестно, строго или нет. Любая задача из NP полиномиально сводится к любой наперёд заданной задаче из NPC. TSP в оптимизационной формулировке(поиск наикратчайшего пути через все вершины) NP-трудна, в формулировке принятия решения (вопрос, существует ли путь через все вершины длины не больше заданной) NP-полна.

[Soul Friend]

Sender в сообщении #1676138 писал(а):

TSP в оптимизационной формулировке(поиск наикратчайшего пути через все вершины) NP-трудна

тогда я имею ввиду это. Не NPC, а NP.

vpb в сообщении #1676087 писал(а):

В известном списке "проблем для сумасшедших" (см., например, "Правила для авторов" "Известий РАН, серия математическая" на портале mathnet.ru ) равенство классов P и NP (проблема Кука) занимает почетное второе место, а первое принадлежит гипотезе Римана.

Задачи на миллион.
Есть смутная идея свести задачу к теоремам и аксиомам в геометрии, а не решать перебором.

[B@R5uk]

Soul Friend в сообщении #1676144 писал(а):

Есть смутная идея свести задачу к теоремам и аксиомам в геометрии, а не решать перебором.

Это эвристика для определённого класса исходных данных задачи. В общем случае вопрос ставится о поиске пути на взвешенном графе, так на нём вообще никакой геометрии нет. Да и в реальности длина дороги может быть больше кратчайшего расстояния на сфере (наглядный пример). Плюс длину порой бывает практичнее измерять не в километрах, а в часах (величина, зависящая от качества дороги и/или используемого средства передвижения, и не являющаяся пропорциональностью) или каких-нибудь в рублях/долларах (а то и вообще некой функцией всех трёх величин). Две точки на противоположных концах континента с точки зрения разъезжего продавца могут оказаться близки, потому что города соединены дешёвым, быстрым и доступным авиарейсом, цена на который укладывается в бюджет.

[Soul Friend]

B@R5uk
Если переменные заданы в $R$ то из-за перемены мест слагаемых (а также изменение их названия ) сумма не меняется.

[B@R5uk]

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

[Soul Friend]

Да я понимаю что подняться на гору не то же самое что спуститься, но если расстояния между точками что в одну что в другую сторону будут равны - задача от этого не будет относиться к $NP$ ?

B@R5uk в сообщении #1676151 писал(а):

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

верно, так как это две разные переменные.

[mihaild]

Soul Friend в сообщении #1676152 писал(а):

задача от этого не будет относиться к $NP$ ?

Если исходная задача относится к NP, то её частный случай тоже.
В любом случае, даже метрический коммивояжер NP-труден.

(Оффтоп)

vpb в сообщении #1676087 писал(а):

равенство классов P и NP (проблема Кука) занимает почетное второе место, а первое принадлежит гипотезе Римана

Удивительно, я бы ожидал обратный порядок. И abc-гипотезу ожидал бы выше гипотезы Римана. Всё же у гипотезы Римана даже формулировка не совсем тривиальная.

[Евгений Машеров]

Soul Friend в сообщении #1676152 писал(а):

Да я понимаю что подняться на гору не то же самое что спуститься, но если расстояния между точками что в одну что в другую сторону будут равны - задача от этого не будет относиться к $NP$ ?

Будет по-прежнему.

-- 23 фев 2025, 21:24 --

mihaild в сообщении #1676153 писал(а):

Удивительно, я бы ожидал обратный порядок. И abc-гипотезу ожидал бы выше гипотезы Римана. Всё же у гипотезы Римана даже формулировка не совсем тривиальная.

Думается, тут в качестве фильтра сам журнал. Чтобы хотя бы знать о его существовании - надо иметь определённые знания.

[Евгений Машеров]

Soul Friend в сообщении #1676144 писал(а):

Есть смутная идея свести задачу к теоремам и аксиомам в геометрии, а не решать перебором.

Если есть потребность в "смутных идеях" - возьмите ту, которую я уж точно не реализую. Копать через линейную алгебру, а не геометрию.
Запишем TSP, как $\min_P \operatorname{tr}PC$, где P - некоторая матрица перестановок, а C - коэффициентов.
Собственные значения матрицы перестановок есть корни из единицы, а основное условие TSP, нераспадение обхода на несколько циклов, означает, что ровно одно из них равно единице. Выбрать в качестве приближения к P некую ортогональную матрицу и изменять её так, чтобы элементы стремились к 0 или 1.