02.01.2014 Опубликовал: Андрей Андрианов

В России решили 2 из 7 математических задач тысячелетия

Челябинский математик Анатолий Васильевич Панюков решил одну из задач тысячелетия, доказал равенство классов P и NP. Эта задача является одной из важнейших задач в теории алгоритмов. Равенство классов P и NP в математическом мире считается одной из актуальных задач тысячелетия (всего этих задач - 7 из них 1 уже решена нашим соотечественником - Перельманом). И заключается в том, что если равенство верно, то большинство актуальных оптимизационных задач можно решить за приемлемое время, например, в бизнесе или на производстве. Сейчас точное решение таких задач основано на переборе, и может занимать более года.

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

Классический пример. Пусть дано множество чисел, например: 50, 2, 47, 5, 21, 4, 78, 1. Задача: можно ли подобрать среди этих чисел такие, что их сумма даст 100? Ответ: можно, например 50+47+2+1 = 100. Проверить верность решения просто. Четыре раза применим операцию сложения и все. Толи дело подобрать эти числа. На первый взгляд это сделать гораздо сложнее. То есть найти решение задачи сложнее, чем его проверить. С точки зрения банальной эрудиции так оно и есть, но математически это не доказано, и остается надежда на то что это не так.

И что с этого? Что с того, если окажется что классы P и NP окажутся равны? Все просто. Равенство классов означает то, что существуют алгоритмы решения многих задач, которые работают гораздо быстрее, чем ныне известные (как было сказано выше).

Естественно, была предпринята далеко не одна попытка доказать или опровергнуть эту гипотезу, но ни одна не увенчалась успехом. Последней, перед Анатолием Панюковым была попытка индийского математика Винэя Деолаликара. По мнению автора формулировки проблемы, Стивена Кука, это решение было «относительно серьёзной попыткой решить проблему P vs NP». Но, к сожалению, в представленном доказательстве был найден ряд ошибок, которые автор пообещал исправить.

Пока математики не нашли ошибки в доказательствах Панюкова. Следующим шагом для признания работы челябинского ученого будет обнародование доказательства в Математическом институте Клэя

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

Равенства классов P и NP – это одна из 7 задач десятилетия – математических проблем, решение которых не могут найти ученые всего мира в течение многих лет. В этот список также входят:

- Гипотеза Ходжа
- Гипотеза Пуанкаре
- Гипотеза Римана
- Теория Янга – Миллса
- Существование и гладкость решений уравнений Навье – Стокса
- Гипотеза Берча – Свиннертон-Дайера


Краткая справка об авторе решения

Панюков Анатолий Васильевич (род. в 1951 г.) Доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики, член ассоциации математического программирования, ученый секретарь Научно-методического совета по математике Министерства образования и науки РФ (Челябинское отделение), член Научно-методического совета Территориального органа Федеральной службы государственной статистики по Челябинской области, член диссертационных советов в Южно-Уральском и Пермском государственных университетах. Автор более 200 научных и учебных публикаций и более 20 изобретений. Руководитель научного семинара «Доказательные вычисления в экономике, технике, естествознании», работа которого поддержана грантами РФФИ, Министерства образования и Международного научно-технического центра. Им подготовлено семь кандидатов и два доктора наук. Имеет звания «Заслуженный работник высшей школы РФ» (2007), «Почетный работник высшего профессионального образования» (2001), «Изобретатель СССР» (1979), награжден медалью Минвуза СССР (1979) и Почётной грамотой Губернатора Челябинской области.

e-mail автора: anatoly.panyukov@gmail.com

Источники:
  1. Интервью с Анатолием Панюковым
    http://www.logoslovo.ru/forum/all/topic_8398/
  2. Описание сути 7-и задач тысячелетия
    http://neudoff.net/blog/nauka-i-texnika/zadachi-tysyacheletiya/ 
  3. Биографическая справка на сайте Южно-Уральского университета
    http://emms.susu.ac.ru/?q=node/9

Теги: Россия, математика

Комментарии


Зеленоградский ВОИР

Салон изобретений и инновационных технологий «Архимед»
Салон изобретений и инновационных технологий «Архимед»
Опубликовал: Андрей Андрианов
Теги: инновации, патенты, изобретательство, салон Архимед, школьники, студенты

Что такое «Главконструктор»?

«Главный конструктор» - проект ресурса по подготовке и продвижению изобретений, на котором осуществляется: организация и проведение экспертизы (для инвесторов), формирование общественного мнения (для продвижения), подготовка социально-адаптированных решений (САР) для «включения» таких решений в планы социально-экономического развития структур и территорий (для государства).

Подробнее о проекте


Статьи

Завтра не наступит
Завтра не наступит
Опубликовал: Андрей Андрианов
Теги: энергетика, будущее, кредит, альтернативная

Школа изобретательства и инноватики

Школа изобретательства: теория и практика. Итоги.
Школа изобретательства: теория и практика. Итоги.
Опубликовал: Вячеслав Локтев
Теги: инновации, обучение, изобретательство, школьники, студенты
Консультации в Школе инноватики и изобретательства.
Консультации в Школе инноватики и изобретательства.
Опубликовал: Андрей Ильичев
Теги: инновации, изобретатели, молодежь, будущее, НТТМ

Теги