2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 14:28 
Sender в сообщении #1522484 писал(а):
Ну, например, одна из известных задач из обсуждаемого класса - это т.н. задача коммивояжёра. Сможете усмотреть кратчайший путь из точки O в точку D, который посещал бы все промежуточные точки ровно по одному разу?

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

 
 
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 14:40 
Outer в сообщении #1522488 писал(а):
Но у меня вопрос - если кто-то заявит, что он нашёл "кратчайший путь" и нарисует его на данной схеме, то каким образом (путём "подстановки результата") можно убедиться в том, что этот путь - на самом деле кратчайший из всех возможных?

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

 
 
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 15:39 
Я думаю, что если решение (< 300) существует, то его можно найти в короткий срок, причём перебирать все варианты для этого необязательно. А если человек является специалистом в данной области и имеет опыт решения таких задач, то он сделает это ещё быстрее.

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

 
 
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение13.06.2021, 15:48 
То, что многие NP-полные задачи в оптимизационной постановке допускают в определённом смысле достаточно эффективное приблизительное решение, не секрет. Но есть и т.н. NP-полные в сильном смысле задачи, для которых таких решений нет (даже с точки зрения специалистов в данной области). В любом случае все эти рассуждения уводят нас от изначальной темы.

 
 
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение17.06.2021, 00:05 
Аватара пользователя
Outer в сообщении #1522436 писал(а):
В то же время, знание предшественников и условий реакции вполне однозначно определяет, что в итоге образуется. Чем это не односторонняя функция?

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

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

 
 
 
 Re: Односторонние функции и отношение классов P и NP
Сообщение17.06.2021, 00:47 
Аватара пользователя
mihaild в сообщении #1523055 писал(а):
Не совсем. Требуется, чтобы если мы взяли случайную строку $x$, нашли $y = f(x)$ и кому-то сообщили $y$, ему было сложно найти $x'$ такое что $f(x') = y$.
В терминах ТС - чтобы по продуктам реакции было сложно найти хоть какую-нибудь реакцию, дающую такие продукты.
Да, спасибо за уточнение.

 
 
 [ Сообщений: 22 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group