Подпишитесь на оповещения
от Газеты.Ru
Дополнительно подписаться
на сообщения раздела СПОРТ
Отклонить
Подписаться
Получать сообщения
раздела Спорт

Индийский Перельман

Индийский математик вслед за Перельманом решил одну из «Задач тысячелетия»

Николай Подорванюк 12.08.2010, 10:49
Thinkstock/Fotobank.ru

Вслед за россиянином Григорием Перельманом, доказавшим гипотезу Пуанкаре, автором решения еще одной «задачи тысячелетия», за которую Институтом имени Клэя (США) положен миллион долларов, возможно, стал индиец Винай Деолаликар. В настоящее время научное сообщество изучает его доказательство неравенства классов сложности P и NP, размером более ста страниц.

«Задачи тысячелетия» представляют собой семь математических проблем, охарактеризованных как «важные классические задачи, решение которых не найдено в течение многих лет». За решение каждой из этих проблем Институтом имени Клэя назначен приз в $1 млн. К настоящему моменту была присуждена только одна премия. За доказательство гипотезы Пуанкаре премия была присуждена российскому математику Григорию Перельману, но он 1 июля отказался от этой премии.

Американский математик индийского происхождения Винай Деолаликар, работающий исследователем в компании HP, утверждает, что решил одну из «Задач тысячелетия».

Несколько дней назад ученый опубликовал доказательство неравенства классов сложности P и NP.

Одной из «задач тысячелетия» является проблема равенства классов сложности P и NP. Данная проблема состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти, то есть действительно ли задачу легче проверить, чем решить? В теории алгоритмов множество вычислительных задач, примерно одинаковых по сложности вычисления, называется классом сложности. Таким образом, если говорить доступным языком, P — это вычислительные задачи, которые легко решить, а NP — задачи, для которых легко проверить, верно ли предполагаемое решение.

Проблема равенства P и NP — это одна из центральных проблем современной информатики.

На предположении неравенства этих классов, которое, вероятно, и доказал Винай Деолаликар, держится большое количество существующих ныне систем защиты информации, от пароля к «аське» до PIN-кода банковской карты.

«Научное сообщество относится к данной заявке довольно серьёзно, — прокомментировал ситуацию «Газете.Ru» доктор физико-математических наук, главный научный сотрудник Математического института имени Стеклова РАН Александр Разборов. — Попытки понять и проверить доказательство предпринимаются наиболее сильными и выдающимися учёными, работающими в этой области. Это, в частности, два филдсовских лауреата. Но даже если отвлечься от чинов, почти все, кто в этом участвует, — наиболее глубокие и уважаемые мною учёные, включая профессора Ричарда Липтона — автора блога, который, по-видимому, становится чем-то вроде общепризнанного пресс-центра по этому делу. Хотя окончательное заключение пока делать, безусловно, преждевременно: уже накопленный материал наводит на мысль о том, что в доказательстве как минимум содержатся серьёзные пробелы. Следует, впрочем, отметить, что большинство вникших в курс дела экспертов сходятся на том, что по крайней мере некоторые идеи автора окажутся интересными сами по себе при любом развитии событий.

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

С тем, что делать выводы о справедливости доказательства индийского математика пока рано, согласен и доктор физико-математических наук, главный научный сотрудник санкт-петербургского отделения Математического института имени Стеклова Анатолий Вершик. «Сейчас еще рано говорить о том, есть ли у индийского ученого решение или нет. Ясно, что речь идет о серьезной заявке: почти 100-страничный текст профессионального математика с неплохим CV. Но серьезных отзывов пока не видно, поэтому надо подождать до разбора текста. На что автор обращает внимание (и это действительно нечастый аргумент в этой области математики) — это то, что будто бы используется вероятностная (или, точнее, статфизическая) идея. Думаю, разбирательство будет недолгим.

Но об одном стоит сказать сейчас: вряд ли нужно ждать от предположительно отрицательного решения проблемы «P=NP» каких-то сугубо прикладных или вычислительных следствий.

Это был бы ожидаемый чисто теоретический результат», — считает ученый.