2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 14:28 


11/10/17
66
Sender в сообщении #1522484 писал(а):
Ну, например, одна из известных задач из обсуждаемого класса - это т.н. задача коммивояжёра. Сможете усмотреть кратчайший путь из точки O в точку D, который посещал бы все промежуточные точки ровно по одному разу?

Кратчайший не смогу, но набросать несколько возможных путей (во всяком случае, не самых длинных) - очевидно, не проблема.
Но у меня вопрос - если кто-то заявит, что он нашёл "кратчайший путь" и нарисует его на данной схеме, то каким образом (путём "подстановки результата") можно убедиться в том, что этот путь - на самом деле кратчайший из всех возможных?

 Профиль  
                  
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 14:40 


14/01/11
2916
Outer в сообщении #1522488 писал(а):
Но у меня вопрос - если кто-то заявит, что он нашёл "кратчайший путь" и нарисует его на данной схеме, то каким образом (путём "подстановки результата") можно убедиться в том, что этот путь - на самом деле кратчайший из всех возможных?

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

 Профиль  
                  
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 15:39 


11/10/17
66
Я думаю, что если решение (< 300) существует, то его можно найти в короткий срок, причём перебирать все варианты для этого необязательно. А если человек является специалистом в данной области и имеет опыт решения таких задач, то он сделает это ещё быстрее.

Кроме того, согласитесь что если речь идёт не о "бумажной задаче", а о реальном поиске короткого пути между городами, то задачу можно решить, к примеру, за пару часов, а для того чтобы реальный автомобиль проехал по этому маршруту (и убедился что предлагаемый путь займет <300 часов), понадобится гораздо больше времени.

 Профиль  
                  
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 15:48 


14/01/11
2916
То, что многие NP-полные задачи в оптимизационной постановке допускают в определённом смысле достаточно эффективное приблизительное решение, не секрет. Но есть и т.н. NP-полные в сильном смысле задачи, для которых таких решений нет (даже с точки зрения специалистов в данной области). В любом случае все эти рассуждения уводят нас от изначальной темы.

 Профиль  
                  
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение17.06.2021, 00:05 
Заслуженный участник
Аватара пользователя


28/04/16
2388
Внутри ускорителя
Outer в сообщении #1522436 писал(а):
В то же время, знание предшественников и условий реакции вполне однозначно определяет, что в итоге образуется. Чем это не односторонняя функция?

:facepalm: Это только в школьной химии так. Предсказание результата реакции какого-нибудь неполного сжигания природного газа -- это нетривиальная задача, очень сложная с точки зрения вычислений.

 Профиль  
                  
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение17.06.2021, 00:40 
Заслуженный участник
Аватара пользователя


16/07/14
8344
Цюрих
Mikhail_K в сообщении #1522442 писал(а):
Требуется, чтобы восстановление аргумента по значению функции было в принципе возможно, но при этом "трудно".
Не совсем. Требуется, чтобы если мы взяли случайную строку $x$, нашли $y = f(x)$ и кому-то сообщили $y$, ему было сложно найти $x'$ такое что $f(x') = y$.
В терминах ТС - чтобы по продуктам реакции было сложно найти хоть какую-нибудь реакцию, дающую такие продукты.
Outer в сообщении #1522508 писал(а):
Я думаю, что если решение (< 300) существует, то его можно найти в короткий срок, причём перебирать все варианты для этого необязательно
Зря вы так думаете.

 Профиль  
                  
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение17.06.2021, 00:47 
Заслуженный участник
Аватара пользователя


26/01/14
4601
mihaild в сообщении #1523055 писал(а):
Не совсем. Требуется, чтобы если мы взяли случайную строку $x$, нашли $y = f(x)$ и кому-то сообщили $y$, ему было сложно найти $x'$ такое что $f(x') = y$.
В терминах ТС - чтобы по продуктам реакции было сложно найти хоть какую-нибудь реакцию, дающую такие продукты.
Да, спасибо за уточнение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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