Челябинский ученый решил одну из семи неразрешимых задач
Математик из Челябинска Анатолий Панюков нашел решение одной из важнейших задач в современной науке.
Как сообщил «Новому Региону» доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики Анатолий Панюков, с 1983 года он занимается решением проблемы равенства классов сложности Р и NP.
Данная задача является одной из важнейших в теории алгоритмов, и одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в 1 миллион долларов США.
В чем суть проблемы равенства классов Р и NP? Есть некий класс задач, для которых можно быстро находить решение (за полиномиальное время), его называют P классом. А есть класс задач, для которых можно быстро проверить правильность их решения, при этом создать алгоритм решения очень сложно – это NP класс. Пока не известно, можно ли, хотя бы в теории, найти такой алгоритм, по которому возможно так же быстро находить решение поставленной задачи, как и проверять его правильность.
Равенство классов означает, что задачи класса NP можно будет решать за полиномиальное время, что сулит огромную выгоду в скорости вычислений. Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время, что считается неприемлемым с практической точки зрения.
По словам челябинского ученого окончательные результаты исследования пока не опубликованы, но своим решением задачи равенства классов P и NP он уже делился с российскими и зарубежными коллегами. Так, свое доказательство Панюков представил на международной конференции в Черногории, а также в Институте математики и механики УрО РАН и в журнале «Автоматика и механика».
Математик сообщил, что он доказал полиномиальную разрешимость одной из сложных NP- полных задач.
Ученый собирается представить, свое решение и в Математический институт Клэя, но для этого необходимо хорошо подготовиться. По словам Анатолия Панюкова, на сегодняшний день в мире существует более 100 вариантов решения данной математической проблемы. Примечательно, что большинство ученых склоняется к тому что классы Р и NP не равны. На данный момент пока ни одно из решений официально не признано.
Отметим, из 7 задач тысячелетия сегодня решена только одна – гипотеза Пуанкаре. В 2002 году российский ученый Григорий Перельман опубликовал серию работ, из которых следует справедливость гипотезы. За это в 2006 году ему была присуждена международная премия «Медаль Филдса» («За вклад в геометрию и его революционные идеи в изучении геометрической и аналитической структуры потока Риччи»). От премии в 1 миллион долларов США ученый отказался.
Комментарии
- дай мильён, дан мильён!:)))
"В каждой естественной науке заключено столько истины, сколько в ней есть математики". И.Кант
Если Вы говорите об эффекте Допплера, то попутали причину и следствие. Не цвет волны (читай - частота) влияет на скорость света, а совсем наоборот.
Мой Вам совет: читайте первоисточники, а не Википедию. Ее пишут дилетанты...
А по поводу СТО... Теорию можно не принимать, но мерилом истины в физике является эксперимент. И я уже упоминал, что теоретические выводы Энштейна с высокой точностью подтверждены эксприментально. Вы летаете самолетами? А знаете, что на скорости 1000 км/час метрическая длина самолета уменьшается примерно на 1 см? Это лоренцево сокращение называется. Лоренц, как Вы говорите, не принял теорию Энштейна. С чего бы он тогда развивал ее?
По сути вы потворствуете нигилистам.
---Гнилые интиллигентишки!!!
Углеродным нанографеном с примесями, как уловитель!!!!)))))
Автор: Редьярд Киплинг
Перевод: В. Лунин
Длинной гирляндой порою ночной
Мчимся мы между землей и луной.
Ты не завидуешь нашим прыжкам,
Скачущим лентам и лишним рукам?
Ты не мечтал, чтоб твой хвост, как тугой
Лук Купидона, был выгнут дугой?
Злишься напрасно ты, Брат! Ерунда!
С гибким хвостом и беда не беда!
Мы поднимаем немыслимый шум.
Головы наши распухли от дум!
Тысячи дел перед нами встают —
Мы их кончаем за пару минут.
Ах, как мудры мы! Ах, как хороши!
Все, что умеем, творим от души.
Всеми забыты мы, Брат? Ерунда!
С гибким хвостом и беда не беда!
....
http://vladivostok.livejournal.com/3095479.html#
Вот только спрашивается, каково прикладное значение его теоремы? Можно ли вывести отсюда другие, более эффективные методы для вычислительных проблем, слывущих "нерешалками"? Верится в такое с большим трудом, даже при всем уважении к поднаторевшим на проблемах теоретической информатики спецам.
На практике может выйти P<nP, а в идеале (цель отладки) должно P=nP/
Если я правильно понял.
И как-то смотришь косо…
Здесь у пацанов к тебе есть пара вопросов…
Может ещё на Руси ещё живы свидетели ... ???