2014 dxdy logo

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

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


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


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



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


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

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
4292
Аделаида
Outer в сообщении #1522436 писал(а):
Но в химии есть такой известный факт - химическое вещество, которое имеет вполне определённую формулу, не зависит от того, как именно оно было получено, и при образовании молекулы, информация о том, как эта молекула была получена, не сохраняется. Например, при сжигании водорода в кислороде образуется вода, при сжигании метана, пропана, бензина, аммиака или любых других водород-содержащих веществ тоже образуется вода (наряду с другими веществами), при пиролизе сахаров также образуется вода и так далее. Во всех случаях образуется одна и та же вода, и по ней невозможно определить её предшественников. В то же время, знание предшественников и условий реакции вполне однозначно определяет, что в итоге образуется.

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

Никак.

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


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

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

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

Почему?

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


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

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

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


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

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


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

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

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


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

 Профиль  
                  
 
 Posted automatically
Сообщение13.06.2021, 12:34 
Заслуженный участник


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

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


14/01/11
2916
Безотносительно к односторонним функциям, 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
4318
Sender в сообщении #1522451 писал(а):
Например

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

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


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

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

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

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

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


14/01/11
2916
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
66
Sender в сообщении #1522467 писал(а):
Возможно, в химии на сегодняшний день и не существует достаточно сложных задач такого класса, но, во-первых, таковые могут появиться в будущем

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

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

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

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

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


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

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

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

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



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

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


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

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