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

TOPIC: P=NP(?)

P=NP(?) 18 Авг 2010 16:43 #31

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

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

P=NP(?) 18 Авг 2010 16:45 #32

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
procrastinator написал(а):
В целом же, обе задачи недостаточно определены. Что мы ищем с распределением студентов? Хоть какое-то расселение, или оптимальное. Если оптимальное, то каков критерий?
согласен. но задача о студентах выложена на сайте института Клея как объяснение проблемы (по ссылке Квантринаса в теме новости науки)

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

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
mittelspiel написал(а):
в состоянии эту задачу решить при помощи хитрых алгоритмов. См например проект folding@home. И из этого вырисовывается для кого-то неутешительный (а для кого-то утешительный) вывод о том, что NP-задачи решаемы.
Я не уверен, что понимаю полностью что такое NP задачи. Можно ли их решить относительно быстро случайным, счастливым образом? Чё-то якобы наличие хитрых алгоритмов вызывает подозрение

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

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Хайдук написал(а):
Я не уверен, что понимаю полностью что такое NP задачи. Можно ли их решить относительно быстро случайным, счастливым образом? Чё-то якобы наличие хитрых алгоритмов вызывает подозрение
Обратимся к первоисточнику по ссылке, предоставленной ув. Крысом:
lenta.ru/articles/2010/08/12/np/
Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза “классы сложности P и NP не равны”. Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной.
А теперь читаем то же самое в оригинале:
www.claymath.org/millennium/P_vs_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.
Last Edit: 23 Окт 2015 13:16 by Vladimirovich.

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

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
А вот формальная формулировка задачи, 12 страниц одна только формулировка, однако

www.claymath.org/millennium/P_vs_NP/pvsnp.pdf
Last Edit: 23 Окт 2015 13:17 by Vladimirovich.

P=NP(?) 19 Авг 2010 00:01 #36

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Миттельшпиль, а Вы знаете про задачу, которую признали за NP и которую можно решить хитрым способом?

P=NP(?) 19 Авг 2010 15:07 #37

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

P=NP(?) 19 Авг 2010 15:21 #38

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
mittelspiel написал(а):
я вот предложил на эту роль задачу о белковом фолдинге
Похоже в ней очень много от биологии, модель слишком сложна и неопределенна, чтобы считать ее за образец такой задачи

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

P=NP(?) 19 Авг 2010 15:27 #39

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Vladimirovich написал(а):
очень много от биологии, модель слишком сложна и неопределенна, чтобы считать ее за образец такой задачи
Если взять реалистические модели, объём вычислений дотягивает до NP?

P=NP(?) 19 Авг 2010 19:37 #40

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Хайдук написал(а):
Vladimirovich написал(а):
очень много от биологии, модель слишком сложна и неопределенна, чтобы считать ее за образец такой задачи
Если взять реалистические модели, объём вычислений дотягивает до NP?
Реалистичность, как мне представляется, не связана напрямую с классом задачи.
Каждому - своё.

P=NP(?) 19 Авг 2010 19:55 #41

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Vladimirovich написал(а):
Реалистичность, как мне представляется, не связана напрямую с классом задачи.
Несомненно, просто хотел усложнить максимально задачу фолдинга белков
. Если не ошибаюсь, суперкомп Blue Gene (вопреки подсказкам которого Веселин проиграл Ананду
) в IBM создавали для решения прежде всего этой задачи, откуда и сама кличка компа. Раз приурочили комп, значит задача не должна быть очень недоступной. Для вычислений в КХД (квантовая хромодинамика) тоже как-будто собирали специализированный комп

P=NP(?) 19 Авг 2010 19:59 #42

  • PP
  • PP's Avatar
  • OFFLINE
  • Холоп
  • Posts: 31409
  • Thank you received: 224
  • Karma: -124
Хайдук написал(а):
в IBM создавали для решения прежде всего этой задачи
Это был лишь рекламный ход. Ничего заточенного под эту задачу блю джин не содержит.

P=NP(?) 09 Сен 2011 18:40 #43

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
А что уважаемые математики думают про это?
www.sandia.gov/LabNews/LN04-21-00/sorin_story.html
Правда ли что в трехмерном случае эту задачу нельзя решить?
Публикации в научном журнале вроде так и не последовало
Last Edit: 23 Окт 2015 13:17 by Vladimirovich.

P=NP(?) 27 Янв 2012 21:02 #44

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
в рунете появился очередной товарищ,
утверждающий что решил проблему p=np.
www.researchgate.net/profile/Sarge_Rogat..._Isomorphism_problem
кроме научного азарта налицо всё признаки
непризнанного гения и фричества.
с элементами антижидомасонского заговора и прочая.
уверен, что дорогой товарищ Лимародесса не пройдет мимо,
и обязательно пригласит его к нашему шалашу

к сожалению мой уровень математики не позволяет мне
понять выкладки предоставленные соискателем.
но уверен, что товарищи Владимирович, Григорий, Serge_P и PP
смогут разобраться лучше.

Отредактировано mittelspiel (2012-01-28 01:03:41)
Last Edit: 23 Окт 2015 13:18 by Vladimirovich.

P=NP(?) 27 Янв 2012 21:12 #45

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
mittelspiel написал(а):
уверен, что дорогой товарищ Лимародесса не пройдет мимо,
Мы верим в него

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

P=NP(?) 27 Янв 2012 21:51 #46

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

Отредактировано mittelspiel (2012-01-28 01:56:29)

P=NP(?) 27 Янв 2012 23:29 #47

  • Serge_P
  • Serge_P's Avatar
  • OFFLINE
  • Бояринъ
  • Posts: 1568
  • Thank you received: 6
  • Karma: 1
mittelspiel написал(а):
но уверен, что товарищи Владимирович, Григорий, Serge_P и PP
смогут разобраться лучше.
тут я - пас. Алгоритмическая сложность - это не моё.

Только, насколько я понимаю, это и не претендует на решение проблемы P=NP. Это другое: en.wikipedia.org/wiki/Graph_isomorphism_problem
Last Edit: 23 Окт 2015 13:18 by Vladimirovich.

P=NP(?) 27 Янв 2012 23:38 #48

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
mittelspiel написал(а):
в рунете появился очередной товарищ,
утверждающий что решил проблему p=np.
Причем тут p=np, это программа якобы решающая Graph Isomorphism problem

P=NP(?) 28 Янв 2012 00:02 #49

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
я не в том смысле что она решает p=np.
а в том смысле что сводит одну из np задач
к решению с временем полиномиальным
а не экспоненциальным.
решение предлагается в виде кода на c++.
текст википедии пытались сегодня скорректировать
в пользу этого решения (по видимому он сам),
но модераторы википедии текст откатили назад.
со скандалом.
в общем любопытный человек, не чета ппг.

Отредактировано mittelspiel (2012-01-28 04:05:05)

P=NP(?) 28 Янв 2012 09:07 #50

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Serge_P написал(а):
тут я - пас.
Я также. Пятикратные циклы и 4-мерные массивы при таком качестве оформления - это рука тянется к пистолету

И вообще я не знаю, честно говоря, на каком основании эта проблема (и вообще проблемы) считается NP
Каждому - своё.

P=NP(?) 28 Янв 2012 14:35 #51

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Vladimirovich написал(а):
Пятикратные циклы и 4-мерные массивы при таком качестве оформления - это рука тянется к пистолету
Выложить код без обсуждения мотивов и алгоритма для проблемы, которая продержалась столько времени это несерьёзно

P=NP(?) 28 Янв 2012 14:37 #52

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

P=NP(?) 29 Янв 2012 12:25 #53

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Вот например ссылочка. Без нее код на С++ будет не очень понятен

webcache.googleusercontent.com/search?q=...&hl=be&ct=clnk&gl=by
Sergey Rogach написал Принцип их действия: забивают людям головы дурью (развлечениями), ложью (в т.ч. под видом шуток); отвлекают от реальной деятельности; опускают самооценку; запугивают; изолируют от важных знаний;
Last Edit: 23 Окт 2015 13:19 by Vladimirovich.

P=NP(?) 09 Фев 2012 01:00 #54

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
самоед написал(а):
математика не исчезнет, но из фундаментальной науки станет инженерной, обслуживающей компьютер
Станет математика более экспериментальной, что ли, эксплуатируя безжалостно компы, но никак не инженерной. Наоборот - комп будет обслуживать навсегда фундаментальную математику

P=NP(?) 09 Фев 2012 05:35 #55

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Хайдук написал(а):
Станет математика более экспериментальной, что ли, эксплуатируя безжалостно компы, но никак не инженерной.
Я думаю, что ув. самоед совершает ту же ошибку, что и wpiter, принимает мат.моделирование за саму математику.
Понятно, что забабахать расчет какой нибудь структурки методом конечных разностей требует для большей точности все больших и больших мощностей. Но это не математика.
Каждому - своё.

P=NP(?) 09 Фев 2012 14:47 #56

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Vladimirovich написал(а):
забабахать расчет какой нибудь структурки методом конечных разностей требует для большей точности все больших и больших мощностей. Но это не математика.

P=NP(?) 09 Фев 2012 16:24 #57

  • самоед
  • самоед's Avatar
  • OFFLINE
  • Самоед
  • Posts: 778
  • Thank you received: 1
  • Karma: 0
Я хотел сказать, что традиционная математика отомрет точно так же, как отомрет традиционная библиотека. А профессиональные математики - подобно инженерам - будут только тем и заниматься, что обучать компьютер все более и более сложной математике, которая в этом обучении будет и состоять, и рождаться. А нематематикам до этого и дела не будет.

P=NP(?) 09 Фев 2012 16:28 #58

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
самоед написал(а):
Я хотел сказать, что традиционная математика отомрет точно так же, как отомрет традиционная библиотека.
А какие у Вас для этого есть основания? Тенденции какие нибудь бы обозначили...

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

P=NP(?) 09 Фев 2012 16:49 #59

  • самоед
  • самоед's Avatar
  • OFFLINE
  • Самоед
  • Posts: 778
  • Thank you received: 1
  • Karma: 0
Vladimirovich написал(а):
А какие у Вас для этого есть основания?..
Запредельный уровень профессиональной компетентногсти.

P=NP(?) 09 Фев 2012 16:57 #60

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
самоед написал(а):
Запредельный уровень профессиональной компетентногсти.
А...
Каждому - своё.
Moderators: Grigoriy
Рейтинг@Mail.ru

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