2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 TSP и P vs NP
Сообщение23.02.2025, 09:07 
Аватара пользователя


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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 12:04 
Заслуженный участник


18/01/15
3312
Soul Friend в сообщении #1676073 писал(а):
то будет ли это означать
Да, будет. Попался как-то текст некоего человека с Урала, Панюков фамилия, который якобы так и сделал. Глянул --- белиберда.

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 12:07 
Заслуженный участник


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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 12:10 
Заслуженный участник


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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 14:51 
Заслуженный участник


12/08/10
1713
Dmitriy40 в сообщении #1676085 писал(а):
все задачи из класса NP сводятся одна к другой
Я читал что это верно для задач NP-complete. Я что-то не так понял?

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 15:33 
Заслуженный участник


20/08/14
11989
Россия, Москва
Null
Нет, тогда скорее это я что-то недопонял.

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 15:33 


14/01/11
3130
Null в сообщении #1676127 писал(а):
Я читал что это верно для задач NP-complete. Я что-то не так понял?

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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 16:04 
Аватара пользователя


12/10/16
662
Almaty, Kazakhstan
Sender в сообщении #1676138 писал(а):
TSP в оптимизационной формулировке(поиск наикратчайшего пути через все вершины) NP-трудна

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

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


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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 17:05 
Аватара пользователя


26/05/12
1780
приходит весна?
Soul Friend в сообщении #1676144 писал(а):
Есть смутная идея свести задачу к теоремам и аксиомам в геометрии, а не решать перебором.
Это эвристика для определённого класса исходных данных задачи. В общем случае вопрос ставится о поиске пути на взвешенном графе, так на нём вообще никакой геометрии нет. Да и в реальности длина дороги может быть больше кратчайшего расстояния на сфере (наглядный пример). Плюс длину порой бывает практичнее измерять не в километрах, а в часах (величина, зависящая от качества дороги и/или используемого средства передвижения, и не являющаяся пропорциональностью) или каких-нибудь в рублях/долларах (а то и вообще некой функцией всех трёх величин). Две точки на противоположных концах континента с точки зрения разъезжего продавца могут оказаться близки, потому что города соединены дешёвым, быстрым и доступным авиарейсом, цена на который укладывается в бюджет.

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 17:19 
Аватара пользователя


12/10/16
662
Almaty, Kazakhstan
B@R5uk
Если переменные заданы в $R$ то из-за перемены мест слагаемых (а также изменение их названия ) сумма не меняется.

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 17:27 
Аватара пользователя


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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 17:45 
Аватара пользователя


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

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


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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 17:52 
Заслуженный участник
Аватара пользователя


16/07/14
9480
Цюрих
Soul Friend в сообщении #1676152 писал(а):
задача от этого не будет относиться к $NP$ ?
Если исходная задача относится к NP, то её частный случай тоже.
В любом случае, даже метрический коммивояжер NP-труден.

(Оффтоп)

vpb в сообщении #1676087 писал(а):
равенство классов P и NP (проблема Кука) занимает почетное второе место, а первое принадлежит гипотезе Римана
Удивительно, я бы ожидал обратный порядок. И abc-гипотезу ожидал бы выше гипотезы Римана. Всё же у гипотезы Римана даже формулировка не совсем тривиальная.

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение23.02.2025, 21:22 
Заслуженный участник
Аватара пользователя


11/03/08
10160
Москва
Soul Friend в сообщении #1676152 писал(а):
Да я понимаю что подняться на гору не то же самое что спуститься, но если расстояния между точками что в одну что в другую сторону будут равны - задача от этого не будет относиться к $NP$ ?


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

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

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


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

 Профиль  
                  
 
 Re: TSP и P vs NP
Сообщение24.02.2025, 08:25 
Заслуженный участник
Аватара пользователя


11/03/08
10160
Москва
Soul Friend в сообщении #1676144 писал(а):
Есть смутная идея свести задачу к теоремам и аксиомам в геометрии, а не решать перебором.


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group