Попробуем отвлечься от общей задачи P=NP(?) и попробовать решить локальную задачку которую предлагают для объяснения:
Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной.
Мне кажется эта задачка довольно просто решается в ряде случаев.
для начала надо бы определиться, является ли эта задачка из класса NP. если да, и если она решаемая, то это означает что теорему в виде PNP доказать невозможно.
Второй пример комбинаторной задачи сложности NP: фолдинг белка. Если бы задача не была решаема за фиксированное время, то мы бы не существовали. Значит задачка белкового фолдинга решаема за конечное фоксированное время (принадлежит к классу P и NP одновременно). То есть теоремка P=NP доказана
для начала надо бы определиться, является ли эта задачка из класса NP. если да, и если она решаемая, то это означает что теорему в виде PNP доказать невозможно.
то, что эта задачка из NP, вроде ясно: если уже предложено конкретное решение, то можно быстро проверить, удовлетворяет ли оно условию задачи. А вот попробуйте доказать, что она не принадлежит P... Т.е., нельзя придумать алгоритм, который за полиномиальное время от количества комнат будет выдавать вариант расселения. Конечно, если ограничений (студентов, которых нельзя селить вместе) очень мало, то тогда почти любой вариант расселения подойдет, и, наверное, можно будет придумать алгоритм, работающий быстро (т.е., задачка будет P). А вот представьте себе ситуацию, что этих ограничений очень много (например, для каждого студента есть лишь несколько возможных соседей); как доказать что нет быстрого алгоритма расселения?
Ответьте на этот вопрос, и можете забирать миллион долларов
Впрочем, если доказать, что быстрый алгоритм есть всегда, то наверное миллион тоже дадут. Где-то я слышал, что такого рода задачки в каком-то смысле эквивалентны: если удастся решить одну, то решаться и остальные (и будет кирдык современным методам шифрования
Конечно, если ограничений (студентов, которых нельзя селить вместе) очень мало, то тогда почти любой вариант расселения подойдет, и, наверное, можно будет придумать алгоритм, работающий быстро (т.е., задачка будет P). А вот представьте себе ситуацию, что этих ограничений очень много (например, для каждого студента есть лишь несколько возможных соседей); как доказать что нет быстрого алгоритма расселения?
Задачка с расселениями слишком расплывчато сформулирована. Очевидно что есть ряд условий при которых она очень просто и быстро решается, но поскольку эти условия не сформулированы, то говорить о них трудно.
Предлагаю обратиться к задаче о белковом фолдинге. Она однозначно сформулирована (есть первичная последовательность, и надо по ней найти третичную структуру). Эта задача, комбинаторно, принадлежит к тому же классу что и задача про студентов (согласны?). Далее, про задачку о фолдинге известно, с физической и с биологической точки зрения, что она имеет быстрое математическое рещение. я не жадный, миллион можно разделить на группу. Предлагаю вот такой путь рещения - сконцентрироваться на одном частном случае (белковый фолдинг) и доказать что для этого случая P=NP. Могу предоставить физические и биологические расклады, а математики добавят формул. В крайнем случае если не дадут миллиона, ограничимся статьей в журнале. Интересует?
Эта задача, комбинаторно, принадлежит к тому же классу что и задача про студентов (согласны?).
Мне это не очевидно, ссылочку не подкинете?
mittelspiel написал(а):
Далее, про задачку о фолдинге известно, с физической и с биологической точки зрения, что она имеет быстрое математическое рещение.
С этим точно не соглсен. Не все быстрые физические процессы имеют быстрое математическое решение. Это имхо ниоткуда не следует. Будет время, попробую привести конкретные примеры.
Это когда линейная последовательность аминокислот сворачивается и принимает трехмерную структуру соответствующую структуре белка. Задача, как зная последовательность, аминокислот предсказать трехмерную структуру. Там лобовой метод минимизации энергии не работает или, по крайней мере, во многих случаях не дает хороший результат.
Это когда линейная последовательность аминокислот сворачивается и принимает трехмерную структуру соответствующую структуре белка. Задача, как зная последовательность, аминокислот предсказать трехмерную структуру. Там лобовой метод минимизации энергии не работает или, по крайней мере, во многих случаях не дает хороший результат.
Лобовой метод нигде не работает. Хитрые алгоритмы существуют. И они работают. На суперкмопьютере или на распределенных кластерах сегодня реально рассчитать фолдинг типичного белка. То ест задача решаемая. Быстро или не быстро - это не количественные показатели. Как это быстро формулируется математически?
Слезно прошу извинить мое невежество, ув. mittelspiel, но я не знаю, что такое белковый фолдинг
Я мог бы поискать в гугле, но если скажете Вы, то получится быстрее
Имеется первичная последовательность аминокислот. Надо предсказать, как они свернутся в трехмерную структуру, в которой функционирует белок.
Не все белки имеют однозначную ттрехмерную структуру. Но для тех белков, которые имеют структуру, задача имеет решение (это очевидно с точки зрения биологии).
Считается, что ускоряет математическую сходимость рещшения задачи о белковом фолдинге то физическое обстоятельство, что к единственному решению (минимуму энергии) ведет множество путей. Схематически это показано на картине:
Я понимаю, что такой тип доказательства для математики не характерен, но он построен на стандартной логике:
1) белок существует и имеет однозначно определенную форму (это не для всех белков, но мы рассматривает только тот класс для которого это выполняется).
2) линейная последовательность аминокислот белка однозначно определяет 3D структуру белка (это не для всех белков, но мы рассматривает только тот класс для которого это выполняется).
3) если решение существует и оно единственно, то могут существовать алогритмы его нахождения
4) алгоритмы белкового фолдинга существуют и их корректность можно проверить сравнив в экспериментом.
5) если существует решение хотя бы одного частного случая, то в общем случае утверждение PNP неверно
если решение существует и оно единственно, то могут существовать алогритмы его нахождения
Могут, а могут и не существовать или не давать решение за конечное число операций
mittelspiel написал(а):
алгоритмы белкового фолдинга существуют и их корректность можно проверить сравнив в экспериментом.
Про эту задачу я знаю мало. Насколько слышал, популярен метод, где берут известную структуру похожего белка и используют, как начальное приближение, что значительно задачу упрощает, но не есть решение оригинальной задачи.
Мне кажется, что задача выходит за рамки математики.
Надо бы знать правила. по которым формируется 3D-структура.
Кроме того, я не понял последнего утверждения
mittelspiel написал(а):
5) если существует решение хотя бы одного частного случая, то в общем случае утверждение PNP неверно
Я правильно понимаю, что речь идет о нахождении частного случая P=NP? Это не будет ничего значить в общем случае.
Я правильно понимаю, что речь идет о нахождении частного случая P=NP? Это не будет ничего значить в общем случае.
Если доказать что задача белкового фолдинга - комбинаторно сложный подлкласс класса NP - имеет решение, то это будет означать что утверждение P не равно NP не выполняется.
Мне кажется, что задача выходит за рамки математики.
Надо бы знать правила. по которым формируется 3D-структура.
Эти правила существуют (есть отрицательные, положительные, нейтральные аминокислоты и разные другие, про которые известны их попарные потенциалы взаимодействия с другими аминокислотами. Мне почему эта задачка всплыла на ум, потому что она аналогична задачке о студентах, про которых деканат спускает правила.
взаимодействия аминокислот - описываются численныеми потенциалами, в отличии от булевких функций которые описывают расселение студентов. Соответственно, абсолютно точно задать потенциал невозможно, но сути дела это не меяет. Каждое улучшение потенциала это новый алгоритм, но даже приближенные значения потенциалов позволяют найти единственное решение задачи фолдинга (решение - тоже не абсолютно точное, но оно сходимое). Наличие сходимости гарантировано существованием энергетической воронки, как на рисунке
но даже приближенные значения потенциалов позволяют найти единственное решение задачи фолдинга.
Я немного сомневаюсь в этом. Если бы все взаимодействия были известны достаточно точно, то можно было бы написать уравнения движения для каждой аминокислоты и тупо в лоб найти стационарное пложение проинтегрировав дифуры. Но раз это не сделано, значит малейшие неточности потенциалов оказывают большое влияние на траектории. Или я туплю?
Я немного сомневаюсь в этом. Если бы все взаимодействия были известны достаточно точно, то можно было бы написать уравнения движения для каждой аминокислоты и тупо в лоб найти стационарное пложение проинтегрировав дифуры. Но раз это не сделано, значит малейшие неточности потенциалов оказывают большое влияние на траектории. Или я туплю?
движения аминокислот стохастические (случайные), их рассчитать нельзя даже зная точные потенциалы взаимодействия, но можно промоделировать методом Монте Карло, например. Это требует затрат на уровне суперкомпьютеров и больших компьютерных кластеров. и в принципе позволяет получать представление о том как оно там в среднем движется. Но это другая задача, отличающаяся от задачи фолдинга, ибо фолдинг это поиск единственной оптимальной конформации (то есть математически соответствует задаче топика, в отличии от стохастических симуляций). А потенциалы взаимодействия - они улучшаются конечно все время, но в общем они существуют.
ибо фолдинг это поиск единственной оптимальной конформации
А вы уверены, что реально белки сворачиваются именно к оптимальному решению? Насколько я помню, они сворачиваются в процессе синтеза, что уже само по себе может привести к локальному оптимуму. К тому же, понятие оптимума нельзя определить без среды, в которой это сворачивание происходит, а это тоже неопределенность.
В целом же, обе задачи недостаточно определены. Что мы ищем с распределением студентов? Хоть какое-то расселение, или оптимальное. Если оптимальное, то каков критерий?
Но это другая задача, отличающаяся от задачи фолдинга, ибо фолдинг это поиск единственной оптимальной конформации
Тоесть, если я тупо задам уравнения движения каждой аминокислоты включив туда стохастический шум, я не получу в виде решения (в статистическом смысле) оптимальную конформацию? Грубо говоря, я говорю о симуляции самого процесса фолдинга, который, как мне казалось и есть процесс движения участков белка приводящий в конце концов к той самой оптимальной структуре. Я то понимаю, что так в лоб эту задачу решить нельзя, просто пытаюсь понять почему. Или дело в неточном знании потенциалов или в чем то еще.
А вы уверены, что реально белки сворачиваются именно к оптимальному решению? Насколько я помню, они сворачиваются в процессе синтеза, что уже само по себе может привести к локальному оптимуму. К тому же, понятие оптимума нельзя определить без среды, в которой это сворачивание происходит, а это тоже неопределенность.
Согласен с вопросом. Подозреваю, что конфигурация белка соответствует достаточно глубокому локальному минимуму энергии, но не глобальному.
Вопрос как Природа решает NP задачи не кажется очень точным. Мы плохо понимаем как происходит самоорганизация большого числа степеней свободы. Наверное многие высокоуровневые эффекты возникают как-бы внезапно, без каких-либо затрат времени и значит (экспоненциальное) число вовлечённых степеней свободы как-бы безразлично
Согласен с вопросом. Подозреваю, что конфигурация белка соответствует достаточно глубокому локальному минимуму энергии, но не глобальному.
Можно разделить белки (грубо, для наших вопросов) на три группы:
1) неструктурированные белки (структура отстутствует, так без структуры и функционируют)
2) белки которые могут существовать в нескольких конформациях (каждой конформации соответствует локальный минимум)
3) белки, которые существуют только в одной конформации (в этом случае она соответствует глобальному энергетическому минимуму)
Не уходя далеко в сторону, можно сказать, что мы рассматриваем, в свете интересующей нас математической задачи, только третий класс белков. Это достаточно большой класс белков, если не самый большой, так что математическая общность не теряется.
Тоесть, если я тупо задам уравнения движения каждой аминокислоты включив туда стохастический шум, я не получу в виде решения (в статистическом смысле) оптимальную конформацию? Грубо говоря, я говорю о симуляции самого процесса фолдинга, который, как мне казалось и есть процесс движения участков белка приводящий в конце концов к той самой оптимальной структуре. Я то понимаю, что так в лоб эту задачу решить нельзя, просто пытаюсь понять почему. Или дело в неточном знании потенциалов или в чем то еще.
В лоб таким образом задачу решить можно, но за бесконечно большое время. Именно поэтому это NP-задача.
Но с другой стороны, мы знаем, что ежесекундно Природа эту задачу весьма успешно решает.
Кроме того, мы знаем, что человек тоже в состоянии эту задачу решить при помощи хитрых алгоритмов. См например проект folding@home.
И из этого вырисовывается для кого-то неутешительный (а для кого-то утешительный) вывод о том, что NP-задачи решаемы.
Можно и так сказать. Броуновское движение, помните, Левенгук под микроскопом увидал. Все частицы все время движутся. Хаотически. В том числе молекулы воды вокруг белка.
Вопрос как Природа решает NP задачи не кажется очень точным. Мы плохо понимаем как происходит самоорганизация большого числа степеней свободы. Наверное многие высокоуровневые эффекты возникают как-бы внезапно, без каких-либо затрат времени и значит (экспоненциальное) число вовлечённых степеней свободы как-бы безразлично
Это да. Но давайте разделим. Одно дело как Природа решает (у нее свой алгоритм), а другое дело как мы на компьютере насчитаем. Если структура совпадает, то и хорошо. На рисунке в начале темы показано, что все дороги ведут вниз в воронку потенциальной энергии, поэтому нважно как решать, ответ один, и ответ достижим за конечное время.
