18.08.2010

Математики окончательно разуверились в решении задачи тысячелетия

Десять дней назад индийский математик Винэй Деолаликар (Vinay Deolalikar) выложил в Cеть статью, в которой, по его утверждению, доказал одно из важнейших неравенств математики - неравенство классов сложности P и NP. Это сообщение вызвало невиданный резонанс среди коллег Деолаликара – ученые забросили свою основную работу и начали массово читать и обсуждать статью. Практически сразу специалисты обнаружили в доказательстве недочеты, а уже через неделю математическое сообщество пришло к выводу, что с поставленной задачей Деолаликар не справился.

Заявка на миллион

Задача о неравенстве классов P и NP – одна из самых интригующих в математике, даром что большинство специалистов и так уверено, что они не равны (все ученые признают, что пока в основу уверенности не положен строгий доказательный фундамент, она будет оставаться в области интуиции, а не науки). Значение этой задачи, которую математический институт Клэя включил в список семи задач тысячелетия, огромно и простирается не только на "умозрительную" математику, но также на компьютерные науки и теории вычислений.

Коротко проблема неравенства классов сложности P и NP формулируется так: "Если положительный ответ на некий вопрос можно быстро проверить, то верно ли, что можно быстро найти ответ на этот вопрос". Задачи, для которых актуальна эта проблема, относятся к классу сложности NP (задачи класса сложности P можно назвать более простыми – в том смысле, что их решение точно можно найти за разумное время).

Один из примеров задач класса сложности NP – вскрытие шифра. На сегодняшний день единственным способом решить эту задачу является перебор всех возможных комбинаций. Этот процесс может занять чудовищно много времени. Но когда верный код найден, злоумышленник моментально поймет, что задача решена (то есть проверку решения можно осуществить за разумное время). В том случае, если классы сложности P и NP все-таки не равны (то есть задачи, решение которых нельзя найти за разумное время, нельзя свести к более простым задачам, которые можно решить быстро), то тогда всем преступникам мира всегда придется вскрывать шифры перебором. Но если вдруг окажется, что неравенство на самом деле является равенством (то есть сложные задачи класса NP можно свести к более простым задачам класса P), то мозговитые воры теоретически смогут придумать более удобный алгоритм, который позволит им взламывать любые шифры намного быстрее.

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

Как всегда случается с проблемами особенной важности, попытки строго доказать, что классы P и NP равны или не равны, предпринимаются регулярно. Обычно заявления на решение задачи тысячелетия делают люди, репутация которых в научном мире, мягко говоря, сомнительна, или даже вовсе любители, не имеющие специального образования, но завороженные масштабностью вызова. Никто из по-настоящему признанных специалистов подобные работы всерьез не принимает, как не относятся всерьез физики к периодическим попыткам доказать, что общая теория относительности или законы Ньютона в корне неверны.

Но в данном случае автором работы, незамысловато названной "P не равно NP" (прочитать текст можно здесь), был не околонаучный безумец, а работающий ученый, причем работающий в очень уважаемом месте – Исследовательских лабораториях Hewlett-Packard в Пало-Альто. Более того, положительный отзыв на его статью дал один из авторов задачи тысячелетия о неравенстве P и NP, Стивен Кук (Stephen Cook). В сопроводительном письме, которое Кук разослал коллегам вместе со статьей (Кук был одним из нескольких ведущих математиков, кому индиец прислал свою работу для ознакомления), он написал, что работа Деолаликара – это "относительно серьезная заявка на доказательство неравенства классов P и NP".

Неизвестно, то ли рекомендация корифея в области теории сложности (именно эта область математики имеет дело с неравенством P и NP) сыграла свою роль, то ли важность самой задачи, но множество математиков из разных стран отвлеклись от своей основной работы и начали разбираться в выкладках Деолаликара. Люди, знающие о неравенстве классов сложности P и NP, но не занимающиеся этой темой непосредственно, также принимали активное участие в обсуждении. Например, они завалили вопросами о доказательстве специалиста по компьютерным наукам Скотта Ааронсона (Scott Aaronson) из Массачусетского технологического института (MIT).

Ааронсон в момент появления статьи Деолаликара был в отпуске и не мог сходу разобраться в доказательстве. Тем не менее, для того чтобы подчеркнуть его важность, он заявил, что отдаст индийцу 200 тысяч долларов, если математическое сообщество и Институт Клэя признают его верным. За этот экстравагантный поступок многие коллеги осудили Ааронсона, заявив, что истинный ученый должен опираться только на факты, а не эпатировать публику красивыми жестами.

Недочёты

Уже в первые дни "обсасывания" статьи Деолаликара специалисты обнаружили в ней несколько серьезных недочетов. Одним из первых, кто публично заявил об этом, был, как ни странно (или, наоборот, совсем не странно), именно Ааронсон. В ответ на укоры читателей его блога в публикации скоропалительных выводов Ааронсон поделился несколькими приемами, которые он использовал для быстрой оценки работы индийца.

Ааронсону, во-первых, не понравилось, что Деолаликар выдержал свою статью не в классической для математиков структуре лемма-теорема-доказательство. Ученый объясняет, что эта придирка вызвана не его врожденным консерватизмом, а тем, что при таком построении работы в ней проще отлавливать "блох". Во-вторых, Ааронсон отметил, что краткое содержание статьи, в котором должно быть объяснено, в чем суть доказательства и как автору удалось преодолеть трудности, которые мешали решить задачу до сих пор, написано чрезвычайно туманно. Наконец, основным моментом, смутившим Ааронсона, стало отсутствие в доказательстве Деолаликара объяснения, как оно может быть применимо для решения некоторых важных частных проблем, связанных с теорией сложности.

Еще через несколько дней Нейл Иммерман (Neil Immerman) из университета штата Массачусетс заявил, что обнаружил в работе индийца "очень серьезный пробел". Соображения Иммермана были опубликованы в блоге специалиста по вычислительным наукам и технике из университета Джорджии Ричарда Липтона (Richard Lipton), где и развернулась основная дискуссия по поводу неравенства P и NP. Ученый апеллировал к тому, что Деолаликар неверно определял задачи, которые попадают в класс сложности NP, но не P, и поэтому все остальные его рассуждения также неправомерны.

Выводы Иммермана заставили даже наиболее лояльных специалистов изменить свою оценку работы индийца с "не исключено, что да" на "практически точно, нет". Более того, математики усомнились даже в том, что из работы Деолаликара удастся извлечь значительное количество идей, которые могут пригодиться при дальнейших попытках разобраться с неравенством. Вердикт математического сообщества (на английском языке и с обилием математических терминов) можно прочитать тут.

Сам Деолаликар на критику коллег ответил, что постарается учесть все замечания в окончательном варианте статьи, который будет подготовлен в ближайшее время (с 6 августа, когда индиец разослал первый вариант своей работы, он уже один раз внес в нее изменения). Если уверения математика окажутся правдивыми и окончательная версия доказательства все же увидит свет, надо думать, что специалисты еще раз изучат приведенные Деолаликаром доводы. Но на сегодняшний день научное сообщество с оценкой уже определилось.

Новый этап?

Даже если отвлечься от важности задач тысячелетия как таковых, у этой истории есть еще одна интересная сторона. Колоссальное по размаху обсуждение работы Деолаликара само по себе является совершенно удивительным событием. Сотни математиков и специалистов по компьютерным наукам бросили все дела и сосредоточились на изучении более чем 100-страничного (sic!) труда индийца. Судя по скорости, с которой ученые обнаружили ошибки, они должны были потратить на прилежное чтение статьи "P не равно NP" немало часов своего свободного – а может, и рабочего - времени. На одном из Википедия-подобных сайтов в срочном порядке была создана страничка, где все желающие могли высказывать свои соображения по поводу приведенного доказательства.

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

Конечно, такой способ получения научных данных пока вызывает много вопросов (самый очевидный - вопрос об авторстве результатов и приоритете открытий), но, в конце концов, большинство новых начинаний первоначально сталкивались с сомнениями и противодействием. Выживание таких начинаний определяется вовсе не отношением общества, а тем, насколько они окажутся востребованы им. И если коллективное обсуждение и получение результатов будет более эффективным, чем традиционные методы научной работы, то очень может быть, что в будущем такая практика станет общепринятой.

Ирина Якутенко

Источники:

1. Lenta.Ru