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

[Outer]

Вот что написано в Википедии про обе мат. проблемы:

1. Одностороняя функция
"Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений.
...Существование односторонних функций до сих пор не доказано. Их существование докажет, что классы сложности P и NP не равны, попутно разрешив ряд вопросов теоретической информатики. Современная асимметричная криптография основывается на предположении, что односторонние функции всё-таки существуют."

2.Равенство классов P и NP
"проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память)? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать? ...Кажется, что подобрать числа сложнее, но это не доказано."


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

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

2. Про отношение классов P и NP говорится, что проверить, является ли предложенное решение какой-либо задачи верным, гораздо проще, чем найти это решение (например, убедиться в том, что потерянный ключ лежит там-то и там-то, гораздо легче чем искать его по всей квартире). Но я приведу такой пример, опять из химии. Допустим, стоит задача разработать способ синтеза какого-либо вещества заданного строения - это может быть лекарство или всё что угодно. В школьном курсе часто предлагают разработать способ синтеза, например, бензола, из угля и любых неорганических веществ. Человек, знакомый с химией, предложит решение очень быстро - из угля (спеканием с известью) можно получить карбид кальция, из него ацетилен, а из ацетилена - бензол. Но если кто-то захочет реально проверить работоспособность такого решения, то ему придётся доставать нужные реагенты, собирать установки для каждой стадии синтеза, проводить анализ продуктов и т.д. И таких примеров в химии много, когда предложить потенциально пригодное решение значительно легче, чем проверить, что это решение будет работать. Как это соотносится с проблемой P vs NP?

[kotenok gav]

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

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

Какое отношение это имеет к математике?

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

Как это соотносится с проблемой P vs NP?

Никак.

[Outer]

kotenok gav в сообщении #1522437 писал(а):

Какое отношение это имеет к математике?

А такое, что продукт реакции является функцией исходных продуктов. Но эти исходные продукты невозможно вывести из конечного результата. Т.е. это пример односторонней функции.

kotenok gav в сообщении #1522437 писал(а):

Никак.

Почему?

[kotenok gav]

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

А такое, что продукт реакции является функцией исходных продуктов. Но эти исходные продукты невозможно вывести из конечного результата. Т.е. это пример односторонней функции.

А $f(x)=1$ тоже пример односторонней функции?

[Mikhail_K]

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

Чем это не односторонняя функция?

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

[Outer]

kotenok gav в сообщении #1522441 писал(а):

А $f(x)=1$ тоже пример односторонней функции?

В Вашем примере всегда получается один и тот же ответ. Но я приведу другой пример - при сжигании какого-то органического вещества образуется смесь продуктов, и она в общем случае неодинаковая для разных органических веществ. Но если например, единственными продуктами сжигания оказались углекислый газ в вода в соотношении, скажем, 1:2, то такой результат может получиться из бесконечного множества исходных соединений. Если их соотношение другое, например, 1:1,8, то исходных вариантов также может быть бесконечное множество.

[kotenok gav]

А $f(x)=10^{\lceil\log_{10}x\rceil}$?

[Pphantom]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»
Причина переноса: в более подходящий раздел.

[Sender]

Безотносительно к односторонним функциям, NP-полнота (или NP-трудность) некоторых задач, возникающих в химии, доказана. Например,
https://pubmed.ncbi.nlm.nih.gov/7831276/,
https://www.nature.com/articles/s41467-019-09440-2.
По-видимому, наиболее прямая связь с NP-полнотой прослеживается в задачах синтеза:
https://core.ac.uk/download/pdf/82275495.pdf.
В наиболее общей постановке задача синтеза алгоритмически неразрешима:
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9276&rep=rep1&type=pdf

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

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

Вообще говоря, можно рассматривать сколь угодно сложные вещества, для которых решение задачи синтеза может оказаться неочевидным (а, соответственно, путь синтеза может оказаться сколь угодно длинным). Например, насколько мне известно, задача о зарождении жизни, рассматриваемая как путь синтеза необходимых органических молекул, включая ДНК, РНК, белки и т.д. из простейших веществ, которые могли существовать на Земле в соответствующий период времени, до сих пор не имеет полного решения. Соответственно, задача нахождения пути синтеза произвольных молекул в общем случае может иметь в разных постановках NP-полную сложность или даже быть алгоритмически неразрешимой.

[Xaositect]

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

[Geen]

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

Например

Обе статьи (в части "алгоритмов") не имеют никакого отношения к химии.

[Outer]

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

В наиболее общей постановке задача синтеза алгоритмически неразрешима

Sender, правильно ли я понимаю, что NP-полные задачи - это те, которые невозможно решить быстро (без перебора всех вариантов), и к ним относятся в т.ч. и задачи синтеза. В то время как человек, в отличие от компьютера, их быстро решает?

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

Например, насколько мне известно, задача о зарождении жизни, рассматриваемая как путь синтеза необходимых органических молекул, включая ДНК, РНК, белки и т.д. из простейших веществ, которые могли существовать на Земле в соответствующий период времени, до сих пор не имеет полного решения.

Путь синтеза отдельных орг. молекул из простейших веществ, в общих чертах известен. Вопрос зарождения жизни сводится не к путям синтеза отдельных молекул, а тому, как они образовали самоподдерживающуюся систему, в которой они работают совместно. Например, погибшая бактерия имеет весь набор ДНК, РНК, белков и т.д., но согласование их работы нарушено, и поэтому эти вещества быстро распадаются.

[Sender]

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

Правильно ли я понимаю, что NP-полные задачи - это те, которые невозможно решить быстро (без перебора всех вариантов), и к ним относятся в т.ч. и задачи синтеза.

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

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

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

Понятно, спасибо.

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

В то время как человек, в отличие от компьютера, их быстро решает?

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

-- Вс июн 13, 2021 13:34:59 --

Geen в сообщении #1522454 писал(а):

Обе статьи (в части "алгоритмов") не имеют никакого отношения к химии.

Ну я не химик по образованию, но разве в первой статье речь не о пространственной структуре белков? В моём школьном курсе химии упоминались вторичные, третичные и четвертичные структуры...

[Outer]

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

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

Могу подтвердить, что их нет.

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

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

Почему? В каких других областях? Из того, что Вы написали, я понял что это и есть основная разница между человеком и компьютером.

Например, если требуется найти козырного туза в колоде карт, то компьютер будет вынужден перебирать все варианты. А если задать вопрос профессионалу в соответствующей области (необязательно химии), то он скажет что "ответ находится примерно там-то и там-то."

[Sender]

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

Почему? В каких других областях? Из того, что Вы написали, я понял что это и есть основная разница между человеком и компьютером.

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