Ключевое слово
22 | 09 | 2019
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: P=NP(?)

P=NP(?) 16 Авг 2010 21:38 #1

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Попробуем отвлечься от общей задачи P=NP(?) и попробовать решить локальную задачку которую предлагают для объяснения:
Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной.
Мне кажется эта задачка довольно просто решается в ряде случаев.

P=NP(?) 17 Авг 2010 16:58 #2

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
математики притихли


для начала надо бы определиться, является ли эта задачка из класса NP. если да, и если она решаемая, то это означает что теорему в виде PNP доказать невозможно.

Второй пример комбинаторной задачи сложности NP: фолдинг белка. Если бы задача не была решаема за фиксированное время, то мы бы не существовали. Значит задачка белкового фолдинга решаема за конечное фоксированное время (принадлежит к классу P и NP одновременно). То есть теоремка P=NP доказана


Отредактировано mittelspiel (2010-08-17 21:06:07)

P=NP(?) 17 Авг 2010 17:15 #3

  • Serge_P
  • Serge_P's Avatar
  • OFFLINE
  • Бояринъ
  • Posts: 1568
  • Thank you received: 6
  • Karma: 1
mittelspiel написал(а):
математики притихли
так дел много


mittelspiel написал(а):
для начала надо бы определиться, является ли эта задачка из класса NP. если да, и если она решаемая, то это означает что теорему в виде PNP доказать невозможно.
то, что эта задачка из NP, вроде ясно: если уже предложено конкретное решение, то можно быстро проверить, удовлетворяет ли оно условию задачи. А вот попробуйте доказать, что она не принадлежит P... Т.е., нельзя придумать алгоритм, который за полиномиальное время от количества комнат будет выдавать вариант расселения. Конечно, если ограничений (студентов, которых нельзя селить вместе) очень мало, то тогда почти любой вариант расселения подойдет, и, наверное, можно будет придумать алгоритм, работающий быстро (т.е., задачка будет P). А вот представьте себе ситуацию, что этих ограничений очень много (например, для каждого студента есть лишь несколько возможных соседей); как доказать что нет быстрого алгоритма расселения?

Ответьте на этот вопрос, и можете забирать миллион долларов


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

P=NP(?) 17 Авг 2010 17:26 #4

  • Крыс
  • Крыс's Avatar
  • OFFLINE
  • Отец Русской Демократии
  • Posts: 33839
  • Thank you received: 60
  • Karma: 13
Serge_P написал(а):
и будет кирдык современным методам шифрования
Пусть нам заплатят миллион и мы не будем решать эту задачу.

P=NP(?) 17 Авг 2010 17:28 #5

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
Serge_P написал(а):
Конечно, если ограничений (студентов, которых нельзя селить вместе) очень мало, то тогда почти любой вариант расселения подойдет, и, наверное, можно будет придумать алгоритм, работающий быстро (т.е., задачка будет P). А вот представьте себе ситуацию, что этих ограничений очень много (например, для каждого студента есть лишь несколько возможных соседей); как доказать что нет быстрого алгоритма расселения?
Разделяю это мнение

Каждому - своё.

P=NP(?) 17 Авг 2010 17:48 #6

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Задачка с расселениями слишком расплывчато сформулирована. Очевидно что есть ряд условий при которых она очень просто и быстро решается, но поскольку эти условия не сформулированы, то говорить о них трудно.

Предлагаю обратиться к задаче о белковом фолдинге. Она однозначно сформулирована (есть первичная последовательность, и надо по ней найти третичную структуру). Эта задача, комбинаторно, принадлежит к тому же классу что и задача про студентов (согласны?). Далее, про задачку о фолдинге известно, с физической и с биологической точки зрения, что она имеет быстрое математическое рещение. я не жадный, миллион можно разделить на группу. Предлагаю вот такой путь рещения - сконцентрироваться на одном частном случае (белковый фолдинг) и доказать что для этого случая P=NP. Могу предоставить физические и биологические расклады, а математики добавят формул. В крайнем случае если не дадут миллиона, ограничимся статьей в журнале. Интересует?

P=NP(?) 17 Авг 2010 17:59 #7

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
mittelspiel написал(а):
Предлагаю обратиться к задаче о белковом фолдинге.
Слезно прошу извинить мое невежество, ув. mittelspiel, но я не знаю, что такое белковый фолдинг

Я мог бы поискать в гугле, но если скажете Вы, то получится быстрее
Каждому - своё.

P=NP(?) 17 Авг 2010 18:06 #8

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 23652
  • Thank you received: 143
  • Karma: 4
mittelspiel написал(а):
Эта задача, комбинаторно, принадлежит к тому же классу что и задача про студентов (согласны?).
Мне это не очевидно, ссылочку не подкинете?

mittelspiel написал(а):
Далее, про задачку о фолдинге известно, с физической и с биологической точки зрения, что она имеет быстрое математическое рещение.
С этим точно не соглсен. Не все быстрые физические процессы имеют быстрое математическое решение. Это имхо ниоткуда не следует. Будет время, попробую привести конкретные примеры.

P=NP(?) 17 Авг 2010 18:08 #9

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 23652
  • Thank you received: 143
  • Karma: 4
Vladimirovich написал(а):
что такое белковый фолдинг
Это когда линейная последовательность аминокислот сворачивается и принимает трехмерную структуру соответствующую структуре белка. Задача, как зная последовательность, аминокислот предсказать трехмерную структуру. Там лобовой метод минимизации энергии не работает или, по крайней мере, во многих случаях не дает хороший результат.

Отредактировано PP (2010-08-17 22:09:11)

P=NP(?) 17 Авг 2010 18:18 #10

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
PP написал(а):
mittelspiel написал(а):

Эта задача, комбинаторно, принадлежит к тому же классу что и задача про студентов (согласны?).

Мне это не очевидно, ссылочку не подкинете?
Такой ссылки нет, и доказать это - часть того что надо сделать чтобы получить миллион. Но я думаю эту часть доказать как раз просто.

P=NP(?) 17 Авг 2010 18:20 #11

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
PP написал(а):
Это когда линейная последовательность аминокислот сворачивается и принимает трехмерную структуру соответствующую структуре белка. Задача, как зная последовательность, аминокислот предсказать трехмерную структуру. Там лобовой метод минимизации энергии не работает или, по крайней мере, во многих случаях не дает хороший результат.
Лобовой метод нигде не работает. Хитрые алгоритмы существуют. И они работают. На суперкмопьютере или на распределенных кластерах сегодня реально рассчитать фолдинг типичного белка. То ест задача решаемая. Быстро или не быстро - это не количественные показатели. Как это быстро формулируется математически?

P=NP(?) 17 Авг 2010 18:26 #12

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Vladimirovich написал(а):
Слезно прошу извинить мое невежество, ув. mittelspiel, но я не знаю, что такое белковый фолдинг

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

Не все белки имеют однозначную ттрехмерную структуру. Но для тех белков, которые имеют структуру, задача имеет решение (это очевидно с точки зрения биологии).

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

P=NP(?) 17 Авг 2010 18:32 #13

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 23652
  • Thank you received: 143
  • Karma: 4
mittelspiel написал(а):
задача имеет решение (это очевидно с точки зрения биологии).
Но не с точки зрения математики.

P=NP(?) 17 Авг 2010 18:40 #14

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
PP написал(а):
Но не с точки зрения математики.
Я понимаю, что такой тип доказательства для математики не характерен, но он построен на стандартной логике:

1) белок существует и имеет однозначно определенную форму (это не для всех белков, но мы рассматривает только тот класс для которого это выполняется).
2) линейная последовательность аминокислот белка однозначно определяет 3D структуру белка (это не для всех белков, но мы рассматривает только тот класс для которого это выполняется).
3) если решение существует и оно единственно, то могут существовать алогритмы его нахождения
4) алгоритмы белкового фолдинга существуют и их корректность можно проверить сравнив в экспериментом.
5) если существует решение хотя бы одного частного случая, то в общем случае утверждение PNP неверно

P=NP(?) 17 Авг 2010 18:45 #15

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 23652
  • Thank you received: 143
  • Karma: 4
mittelspiel написал(а):
если решение существует и оно единственно, то могут существовать алогритмы его нахождения
Могут, а могут и не существовать или не давать решение за конечное число операций

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

P=NP(?) 17 Авг 2010 18:46 #16

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
Мне кажется, что задача выходит за рамки математики.
Надо бы знать правила. по которым формируется 3D-структура.
Кроме того, я не понял последнего утверждения

mittelspiel написал(а):
5) если существует решение хотя бы одного частного случая, то в общем случае утверждение PNP неверно
Я правильно понимаю, что речь идет о нахождении частного случая P=NP? Это не будет ничего значить в общем случае.
Каждому - своё.

P=NP(?) 17 Авг 2010 19:14 #17

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Vladimirovich написал(а):
Я правильно понимаю, что речь идет о нахождении частного случая P=NP? Это не будет ничего значить в общем случае.
Если доказать что задача белкового фолдинга - комбинаторно сложный подлкласс класса NP - имеет решение, то это будет означать что утверждение P не равно NP не выполняется.

P=NP(?) 17 Авг 2010 19:16 #18

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Vladimirovich написал(а):
Мне кажется, что задача выходит за рамки математики.
Надо бы знать правила. по которым формируется 3D-структура.
Эти правила существуют (есть отрицательные, положительные, нейтральные аминокислоты и разные другие, про которые известны их попарные потенциалы взаимодействия с другими аминокислотами. Мне почему эта задачка всплыла на ум, потому что она аналогична задачке о студентах, про которых деканат спускает правила.

P=NP(?) 17 Авг 2010 19:29 #19

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 23652
  • Thank you received: 143
  • Karma: 4
mittelspiel написал(а):
про которые известны их попарные потенциалы взаимодействия с другими аминокислотами.
Разве абсолютно точно известны?

P=NP(?) 17 Авг 2010 19:57 #20

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
PP написал(а):
Разве абсолютно точно известны?
взаимодействия аминокислот - описываются численныеми потенциалами, в отличии от булевких функций которые описывают расселение студентов. Соответственно, абсолютно точно задать потенциал невозможно, но сути дела это не меяет. Каждое улучшение потенциала это новый алгоритм, но даже приближенные значения потенциалов позволяют найти единственное решение задачи фолдинга (решение - тоже не абсолютно точное, но оно сходимое). Наличие сходимости гарантировано существованием энергетической воронки, как на рисунке

Отредактировано mittelspiel (2010-08-18 00:03:44)

P=NP(?) 17 Авг 2010 20:11 #21

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 23652
  • Thank you received: 143
  • Karma: 4
mittelspiel написал(а):
но даже приближенные значения потенциалов позволяют найти единственное решение задачи фолдинга.
Я немного сомневаюсь в этом. Если бы все взаимодействия были известны достаточно точно, то можно было бы написать уравнения движения для каждой аминокислоты и тупо в лоб найти стационарное пложение проинтегрировав дифуры. Но раз это не сделано, значит малейшие неточности потенциалов оказывают большое влияние на траектории. Или я туплю?

P=NP(?) 17 Авг 2010 21:32 #22

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
PP написал(а):
Я немного сомневаюсь в этом. Если бы все взаимодействия были известны достаточно точно, то можно было бы написать уравнения движения для каждой аминокислоты и тупо в лоб найти стационарное пложение проинтегрировав дифуры. Но раз это не сделано, значит малейшие неточности потенциалов оказывают большое влияние на траектории. Или я туплю?
движения аминокислот стохастические (случайные), их рассчитать нельзя даже зная точные потенциалы взаимодействия, но можно промоделировать методом Монте Карло, например. Это требует затрат на уровне суперкомпьютеров и больших компьютерных кластеров. и в принципе позволяет получать представление о том как оно там в среднем движется. Но это другая задача, отличающаяся от задачи фолдинга, ибо фолдинг это поиск единственной оптимальной конформации (то есть математически соответствует задаче топика, в отличии от стохастических симуляций). А потенциалы взаимодействия - они улучшаются конечно все время, но в общем они существуют.

Отредактировано mittelspiel (2010-08-18 01:38:32)

P=NP(?) 17 Авг 2010 22:00 #23

  • Автор: procrastinator
  • Автор: procrastinator's Avatar
ибо фолдинг это поиск единственной оптимальной конформации
А вы уверены, что реально белки сворачиваются именно к оптимальному решению? Насколько я помню, они сворачиваются в процессе синтеза, что уже само по себе может привести к локальному оптимуму. К тому же, понятие оптимума нельзя определить без среды, в которой это сворачивание происходит, а это тоже неопределенность.
В целом же, обе задачи недостаточно определены. Что мы ищем с распределением студентов? Хоть какое-то расселение, или оптимальное. Если оптимальное, то каков критерий?

P=NP(?) 17 Авг 2010 22:01 #24

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 23652
  • Thank you received: 143
  • Karma: 4
mittelspiel написал(а):
движения аминокислот стохастические
Из-за окружающей среды?

mittelspiel написал(а):
Но это другая задача, отличающаяся от задачи фолдинга, ибо фолдинг это поиск единственной оптимальной конформации
Тоесть, если я тупо задам уравнения движения каждой аминокислоты включив туда стохастический шум, я не получу в виде решения (в статистическом смысле) оптимальную конформацию? Грубо говоря, я говорю о симуляции самого процесса фолдинга, который, как мне казалось и есть процесс движения участков белка приводящий в конце концов к той самой оптимальной структуре. Я то понимаю, что так в лоб эту задачу решить нельзя, просто пытаюсь понять почему. Или дело в неточном знании потенциалов или в чем то еще.

P=NP(?) 18 Авг 2010 01:37 #25

  • Quantrinas
  • Quantrinas's Avatar
  • OFFLINE
  • Физик
  • Posts: 12016
  • Thank you received: 4
  • Karma: 0
procrastinator написал(а):
А вы уверены, что реально белки сворачиваются именно к оптимальному решению? Насколько я помню, они сворачиваются в процессе синтеза, что уже само по себе может привести к локальному оптимуму. К тому же, понятие оптимума нельзя определить без среды, в которой это сворачивание происходит, а это тоже неопределенность.
Согласен с вопросом. Подозреваю, что конфигурация белка соответствует достаточно глубокому локальному минимуму энергии, но не глобальному.

P=NP(?) 18 Авг 2010 14:37 #26

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 37872
  • Thank you received: 85
  • Karma: 22
Вопрос как Природа решает NP задачи не кажется очень точным. Мы плохо понимаем как происходит самоорганизация большого числа степеней свободы. Наверное многие высокоуровневые эффекты возникают как-бы внезапно, без каких-либо затрат времени и значит (экспоненциальное) число вовлечённых степеней свободы как-бы безразлично

P=NP(?) 18 Авг 2010 16:30 #27

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Quantrinas написал(а):
Согласен с вопросом. Подозреваю, что конфигурация белка соответствует достаточно глубокому локальному минимуму энергии, но не глобальному.
Можно разделить белки (грубо, для наших вопросов) на три группы:
1) неструктурированные белки (структура отстутствует, так без структуры и функционируют)
2) белки которые могут существовать в нескольких конформациях (каждой конформации соответствует локальный минимум)
3) белки, которые существуют только в одной конформации (в этом случае она соответствует глобальному энергетическому минимуму)

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

P=NP(?) 18 Авг 2010 16:34 #28

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
PP написал(а):
Тоесть, если я тупо задам уравнения движения каждой аминокислоты включив туда стохастический шум, я не получу в виде решения (в статистическом смысле) оптимальную конформацию? Грубо говоря, я говорю о симуляции самого процесса фолдинга, который, как мне казалось и есть процесс движения участков белка приводящий в конце концов к той самой оптимальной структуре. Я то понимаю, что так в лоб эту задачу решить нельзя, просто пытаюсь понять почему. Или дело в неточном знании потенциалов или в чем то еще.
В лоб таким образом задачу решить можно, но за бесконечно большое время. Именно поэтому это NP-задача.
Но с другой стороны, мы знаем, что ежесекундно Природа эту задачу весьма успешно решает.
Кроме того, мы знаем, что человек тоже в состоянии эту задачу решить при помощи хитрых алгоритмов. См например проект folding@home.
И из этого вырисовывается для кого-то неутешительный (а для кого-то утешительный) вывод о том, что NP-задачи решаемы.

P=NP(?) 18 Авг 2010 16:37 #29

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
PP написал(а):
mittelspiel написал(а):

движения аминокислот стохастические

Из-за окружающей среды?
Можно и так сказать. Броуновское движение, помните, Левенгук под микроскопом увидал. Все частицы все время движутся. Хаотически. В том числе молекулы воды вокруг белка.

P=NP(?) 18 Авг 2010 16:40 #30

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Хайдук написал(а):
Вопрос как Природа решает NP задачи не кажется очень точным. Мы плохо понимаем как происходит самоорганизация большого числа степеней свободы. Наверное многие высокоуровневые эффекты возникают как-бы внезапно, без каких-либо затрат времени и значит (экспоненциальное) число вовлечённых степеней свободы как-бы безразлично
Это да. Но давайте разделим. Одно дело как Природа решает (у нее свой алгоритм), а другое дело как мы на компьютере насчитаем. Если структура совпадает, то и хорошо. На рисунке в начале темы показано, что все дороги ведут вниз в воронку потенциальной энергии, поэтому нважно как решать, ответ один, и ответ достижим за конечное время.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум