2014 dxdy logo

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

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


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


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



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


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

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

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


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

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

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

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


21/05/16
4095
Аделаида
Outer в сообщении #1522436 писал(а):
Но в химии есть такой известный факт - химическое вещество, которое имеет вполне определённую формулу, не зависит от того, как именно оно было получено, и при образовании молекулы, информация о том, как эта молекула была получена, не сохраняется. Например, при сжигании водорода в кислороде образуется вода, при сжигании метана, пропана, бензина, аммиака или любых других водород-содержащих веществ тоже образуется вода (наряду с другими веществами), при пиролизе сахаров также образуется вода и так далее. Во всех случаях образуется одна и та же вода, и по ней невозможно определить её предшественников. В то же время, знание предшественников и условий реакции вполне однозначно определяет, что в итоге образуется.

Какое отношение это имеет к математике?
Outer в сообщении #1522436 писал(а):
Как это соотносится с проблемой P vs NP?

Никак.

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


11/10/17
35
kotenok gav в сообщении #1522437 писал(а):
Какое отношение это имеет к математике?

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

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

Почему?

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


21/05/16
4095
Аделаида
Outer в сообщении #1522439 писал(а):
А такое, что продукт реакции является функцией исходных продуктов. Но эти исходные продукты невозможно вывести из конечного результата. Т.е. это пример односторонней функции.

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

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


26/01/14
3832
Outer в сообщении #1522436 писал(а):
Чем это не односторонняя функция?
Требуется, чтобы восстановление аргумента по значению функции было в принципе возможно, но при этом "трудно". Причём трудно не в бытовом смысле, а именно в смысле теории сложности вычислений.

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


11/10/17
35
kotenok gav в сообщении #1522441 писал(а):
А $f(x)=1$ тоже пример односторонней функции?

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

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


21/05/16
4095
Аделаида
А $f(x)=10^{\lceil\log_{10}x\rceil}$?

 Профиль  
                  
 
 Posted automatically
Сообщение13.06.2021, 12:34 
Супермодератор
Аватара пользователя


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

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


14/01/11
2654
Безотносительно к односторонним функциям, 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-полную сложность или даже быть алгоритмически неразрешимой.

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


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

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


01/09/13
3134
Sender в сообщении #1522451 писал(а):
Например

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

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


11/10/17
35
Sender в сообщении #1522451 писал(а):
В наиболее общей постановке задача синтеза алгоритмически неразрешима

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

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

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

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


14/01/11
2654
Outer в сообщении #1522458 писал(а):
Правильно ли я понимаю, что NP-полные задачи - это те, которые невозможно решить быстро (без перебора всех вариантов), и к ним относятся в т.ч. и задачи синтеза.

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

Понятно, спасибо.
Outer в сообщении #1522458 писал(а):
В то время как человек, в отличие от компьютера, их быстро решает?

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

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

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

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

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


11/10/17
35
Sender в сообщении #1522467 писал(а):
Возможно, в химии на сегодняшний день и не существует достаточно сложных задач такого класса, но, во-первых, таковые могут появиться в будущем

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

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

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

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

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


14/01/11
2654
Outer в сообщении #1522473 писал(а):
Почему? В каких других областях? Из того, что Вы написали, я понял что это и есть основная разница между человеком и компьютером.

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

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

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



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

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


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

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