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

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

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

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

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

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

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

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

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

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

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

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