Односторонние функции и отношение классов P и NP

[Outer]

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

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

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

[Sender]

Outer в сообщении #1522488 писал(а):

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

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

[Outer]

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

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

[Sender]

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

[madschumacher]

Outer в сообщении #1522436 писал(а):

В то же время, знание предшественников и условий реакции вполне однозначно определяет, что в итоге образуется. Чем это не односторонняя функция?

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

[mihaild]

Mikhail_K в сообщении #1522442 писал(а):

Требуется, чтобы восстановление аргумента по значению функции было в принципе возможно, но при этом "трудно".

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

Outer в сообщении #1522508 писал(а):

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

Зря вы так думаете.

[Mikhail_K]

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

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

Да, спасибо за уточнение.