А вы уверены, что реально белки сворачиваются именно к оптимальному решению? Насколько я помню, они сворачиваются в процессе синтеза, что уже само по себе может привести к локальному оптимуму.
может. но не приводит насколько мне известно (хотя в этом я могу ошибаться).
а очередность сворачивания - это особенность алгоритма который используется в живой клетке. Но как уже указывалось, много можно алгоритмов построить, и такой тоже.
В целом же, обе задачи недостаточно определены. Что мы ищем с распределением студентов? Хоть какое-то расселение, или оптимальное. Если оптимальное, то каков критерий?
согласен. но задача о студентах выложена на сайте института Клея как объяснение проблемы (по ссылке Квантринаса в теме новости науки)
в состоянии эту задачу решить при помощи хитрых алгоритмов. См например проект folding@home. И из этого вырисовывается для кого-то неутешительный (а для кого-то утешительный) вывод о том, что NP-задачи решаемы.
Я не уверен, что понимаю полностью что такое NP задачи. Можно ли их решить относительно быстро случайным, счастливым образом? Чё-то якобы наличие хитрых алгоритмов вызывает подозрение
Я не уверен, что понимаю полностью что такое NP задачи. Можно ли их решить относительно быстро случайным, счастливым образом? Чё-то якобы наличие хитрых алгоритмов вызывает подозрение
Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза “классы сложности P и NP не равны”. Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной.
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
Реалистичность, как мне представляется, не связана напрямую с классом задачи.
Несомненно, просто хотел усложнить максимально задачу фолдинга белков
. Если не ошибаюсь, суперкомп Blue Gene (вопреки подсказкам которого Веселин проиграл Ананду
) в IBM создавали для решения прежде всего этой задачи, откуда и сама кличка компа. Раз приурочили комп, значит задача не должна быть очень недоступной. Для вычислений в КХД (квантовая хромодинамика) тоже как-будто собирали специализированный комп
А что уважаемые математики думают про это? www.sandia.gov/LabNews/LN04-21-00/sorin_story.html
Правда ли что в трехмерном случае эту задачу нельзя решить?
Публикации в научном журнале вроде так и не последовало
в рунете появился очередной товарищ,
утверждающий что решил проблему p=np. www.researchgate.net/profile/Sarge_Rogat..._Isomorphism_problem
кроме научного азарта налицо всё признаки
непризнанного гения и фричества.
с элементами антижидомасонского заговора и прочая.
уверен, что дорогой товарищ Лимародесса не пройдет мимо,
и обязательно пригласит его к нашему шалашу
к сожалению мой уровень математики не позволяет мне
понять выкладки предоставленные соискателем.
но уверен, что товарищи Владимирович, Григорий, Serge_P и PP
смогут разобраться лучше.
да, поскольку уровень проблемы на порядок выше той, за которую Перельман получил Филдсовскую медаль. то свои слова про фричество я временно отзываю. До тех пор пока форумные эксперты не выскажутся.
я не в том смысле что она решает p=np.
а в том смысле что сводит одну из np задач
к решению с временем полиномиальным
а не экспоненциальным.
решение предлагается в виде кода на c++.
текст википедии пытались сегодня скорректировать
в пользу этого решения (по видимому он сам),
но модераторы википедии текст откатили назад.
со скандалом.
в общем любопытный человек, не чета ппг.
Sergey Rogach написал Принцип их действия: забивают людям головы дурью (развлечениями), ложью (в т.ч. под видом шуток); отвлекают от реальной деятельности; опускают самооценку; запугивают; изолируют от важных знаний;
математика не исчезнет, но из фундаментальной науки станет инженерной, обслуживающей компьютер
Станет математика более экспериментальной, что ли, эксплуатируя безжалостно компы, но никак не инженерной. Наоборот - комп будет обслуживать навсегда фундаментальную математику
Станет математика более экспериментальной, что ли, эксплуатируя безжалостно компы, но никак не инженерной.
Я думаю, что ув. самоед совершает ту же ошибку, что и wpiter, принимает мат.моделирование за саму математику.
Понятно, что забабахать расчет какой нибудь структурки методом конечных разностей требует для большей точности все больших и больших мощностей. Но это не математика.
забабахать расчет какой нибудь структурки методом конечных разностей требует для большей точности все больших и больших мощностей. Но это не математика.
Я хотел сказать, что традиционная математика отомрет точно так же, как отомрет традиционная библиотека. А профессиональные математики - подобно инженерам - будут только тем и заниматься, что обучать компьютер все более и более сложной математике, которая в этом обучении будет и состоять, и рождаться. А нематематикам до этого и дела не будет.