Челябинский ученый решил одну из семи неразрешимых задач тысячелетия
Он доказал равенство классов сложности Р и NP  16.12.13 14:23

Обсудить (12)
Версия для печати
Мобильная версия

Челябинск, Декабрь 16 (Новый Регион, Юлия Малецкая) – Математик из Челябинска Анатолий Панюков нашел решение одной из важнейших задач в современной науке.

Как сообщил «Новому Региону» доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики Анатолий Панюков, с 1983 года он занимается решением проблемы равенства классов сложности Р и NP.

Данная задача является одной из важнейших в теории алгоритмов, и одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в 1 миллион долларов США.

В чем суть проблемы равенства классов Р и NP? Есть некий класс задач, для которых можно быстро находить решение (за полиномиальное время), его называют P классом. А есть класс задач, для которых можно быстро проверить правильность их решения, при этом создать алгоритм решения очень сложно – это NP класс. Пока не известно, можно ли, хотя бы в теории, найти такой алгоритм, по которому возможно так же быстро находить решение поставленной задачи, как и проверять его правильность.

Равенство классов означает, что задачи класса NP можно будет решать за полиномиальное время, что сулит огромную выгоду в скорости вычислений. Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время, что считается неприемлемым с практической точки зрения.

Подпишитесь на новости «Новый Регион – Челябинск» ВКонтакте >>>

По словам челябинского ученого окончательные результаты исследования пока не опубликованы, но своим решением задачи равенства классов P и NP он уже делился с российскими и зарубежными коллегами. Так, свое доказательство Панюков представил на международной конференции в Черногории, а также в Институте математики и механики УрО РАН и в журнале «Автоматика и механика».

Математик сообщил, что он доказал полиномиальную разрешимость одной из сложных NP- полных задач.

Ученый собирается представить, свое решение и в Математический институт Клэя, но для этого необходимо хорошо подготовиться. По словам Анатолия Панюкова, на сегодняшний день в мире существует более 100 вариантов решения данной математической проблемы. Примечательно, что большинство ученых склоняется к тому что классы Р и NP не равны. На данный момент пока ни одно из решений официально не признано.

Отметим, из 7 задач тысячелетия сегодня решена только одна – гипотеза Пуанкаре. В 2002 году российский ученый Григорий Перельман опубликовал серию работ, из которых следует справедливость гипотезы. За это в 2006 году ему была присуждена международная премия «Медаль Филдса» («За вклад в геометрию и его революционные идеи в изучении геометрической и аналитической структуры потока Риччи»). От премии в 1 миллион долларов США ученый отказался.
NR2.ru: http://nr2.ru/chel/475997.html