Хотя выражение P=NP и не приобрело такой поп-культурной известности, как физическая формула E=MC2, его периодически можно встретить в местах, казалось бы, совсем неожиданных Математические блоги шумят как улей: никому не известный сотрудник лаборатории Hewlett-Packard в Пало-Альто, индиец по национальности, опубликовал огромную статью, претендующую на окончательное решение одной из главных открытых проблем математики. К настоящему моменту в проверяемом всем миром доказательстве уже нашли ошибки, в нахождении которых также нашли ошибки, в которых… В общем – надо разобраться, что же произошло.
Предыстория такова. В субботу 7 августа небезызвестный математик Стив Кук (Stephen Arthur Cook) отправил по электронной почте коллегам из университета Торонто (UT) и некоторым своим бывшим аспирантам PDF-файл, пришедший к нему чуть ранее. Тем самым он завёл часовой механизм бомбы, которой было суждено «взорвать» математический мир.
В 116-страничном документе предлагался оригинальный комплексный способ решения задачи о , в 1971 году Куком и сформулированной.
В чём же суть фразы «классы сложности P и NP не равны»? Если говорить совсем грубо, то P – это класс задач, которые мы умеем быстро решать, а NP – класс задач, у которых мы быстро умеем проверять правильность решения. Или проще и в вопросительной форме: если имеющееся положительное решение задачи можно быстро проверить, можно ли его столь же быстро найти? (иллюстрация amazon.com/Appalachian State University/MIT)
Представшее взору Стивена доказательство разительно отличалось от прочих уже по уровню аргументации. Явных ошибок в работе человека по имени Винэй Деолаликар (Vinay Deolalikar) математик сходу не нашёл и передал бумагу для проверки «второму эшелону». (По-видимому, он решил особо не зарываться, поскольку привлечённая автором конечная теория моделей не входила в сферу компетенции Кука.)
Далее события развивались с завидной скоростью. Один из аспирантов переслал письмо сразу всему факультету информатики ванкуверского отделения университета Саймона Фрейзера (SFU) с комментарием в духе «Одобрено самим Стивом Куком». Почти сразу же информация попала на портал Slashdot, а на следующий день математик Грэг Бэйкер (Grag Baker) также в своём блоге отправленную ему копию доказательства.
В результате уже к началу недели весь Интернет был в курсе событий. Из-за масштабности замаха, который сделал Деолаликар, новость о его доказательстве достаточно быстро попала и на страницы ведущих новостных агентств и научных сайтов – от BBC до Nature.
Причина шумихи проста. Эта математическая проблема входит в список семи (Millenium Prize), за решение каждой из которых полагается $1 миллион. Широкий общественный резонанс эта премия получила после серии необычных поступков Григория Перельмана, успешно доказавшего гипотезу Пуанкаре – первую задачу из семи.
С начала семидесятых, когда был сформулирован вопрос о равенстве/неравенстве классов сложности P и NP, учёные всеми возможными методами, оказывавшимися одинаково безуспешными, пытались найти ответ на задачу тысячелетия.
В числе энтузиастов не только и не столько исследователи, интересующиеся фундаментальными аспектами математики, сколько понимающие важность темы специалисты по теории компьютерных вычислений и шифрования данных.
Диаграмма классов сложности задач при условии, что P и NP неравны. С виду простая схема на деле оборачивается десятками страниц математических формул (иллюстрация Journal of Universal Computer Science).
Задачи класса сложности P можно решить «эффективно», за адекватное время (в науке устоялся термин «полиномиальное время», означающий, что время решения задачи не превосходит полинома от размера данных). В класс NP, условно говоря, входят проблемы, которые поддаются проверке с помощью компьютера: действительно ли данный кандидат на решение таковым и является.
Если ответ на вопрос «равны ли P и NP» — положителен, это означает, что любую задачу, для которой решение «быстро» проверяется, можно и решить «быстро». Пример: верно ли, что среди ряда чисел {−2, −3, 15, 14, 7, −10, ...} есть такие, что их сумма равняется 0 (т.н. задача о суммах подмножеств)?
Ответ здесь положителен, потому что он легко проверяется несколькими сложениями. Но вот следует ли отсюда, что эти числа так же легко подобрать?
Деолаликар представил доказательство, что нет. То есть, что P не равно NP. На стороне такого утверждения давно уже была математическая интуиция исследователей. Собственно, исходное неравенство классов P и NP лежит в основе самых популярных криптографических алгоритмов.
Характерный пример задачи класса сложности NP – сборка мозаики вслепую. С одной стороны, вы легко можете определить, правильно ли уложены все кусочки, с другой, получить осмысленное изображение из сотен разноцветных фрагментов уже не так просто.
В математической среде равенство P и NP уже давно стало своеобразным весёлым мемом (смотрите. «наглядную формулировку»), вопросом, на разрешение которого в ближайшее время всерьёз никто не надеялся. Хотя, к примеру, на сайте технологического университета Эйндховена опубликован огромный список «расстрелянных» гипотез, чьи создатели и доказывали, и опровергали неравенство, и вообще объявляли его недоказуемым (фото Discover Magazine/zazzle.com).
Если новое доказательство Деолаликара выдержит проверку (к текущему моменту в нём уже сотни раз находили «дыры» и вновь «чинили»), значит, и вправду есть задачи, решение которых быстро проверяется, но искать его придётся долго. На практике это принесёт миру теоретическое подтверждение, что криптографические коды, которые невозможно взломать за разумное время, действительно совершенны. Доказательство же обратного (что P=NP) и вовсе перевернуло бы программирование.
Поясним, в современных шифрах используют технологию больших чисел, то есть передаваемая информация кодируется огромным количеством цифр, и на вскрытие этого кода придётся потратить столько времени, что эта задача лишается смысла. Даже когда вы посылаете реквизиты карты на адрес магазина, они отправляются туда в зашифрованном всё по тому же принципу виде.
Если это не так – то «возможно всё» и стоит поставить под сомнение сам принцип такого кодирования. Впрочем, нынешнее доказательство посвящено обратному. Пока статья индийского математика не опубликована в рецензируемом журнале, но можно посмотреть её полный текст в PDF-документе. Кстати, статьи того же Перельмана, за которые ему присудили Премию тысячелетия, так никогда и не были официально опубликованы.
«Отряд проверки» из нескольких элитных математиков во главе с профессором Калифорнийского университета в Лос-Анджелесе Теренсом Тао (Terence Tao) на текущий момент нашёл несколько ошибок, которые, по оценкам «инспекторов», являются непоправимыми. Подробнее о них можно прочесть в блоге Ричарда Липтона (R. J. Lipton) из технологического института Джорджии (Georgia Tech.)
Однако в любом случае, даже если окажется, что индийский математик не прав, «отряд проверки» предлагает ряд других прорывных задач. Для их решения можно применить новаторский подход Деолаликара, привлекая не только конечную теорию моделей, но и статистическую физику.
«Если неравенство P и NP действительно будет доказано, моя жизнь изменится настолько кардинально, что потеря 200 тысяч будет совершенно неощутима», – говорит Скотт Аронсон, один из главных оппонентов индийского самородка (фото MIT).
Сотрудник Массачусетского технологического института Скотт Аронсон (Scott Aaronson) изначально был настроен вполне оптимистично – в своём блоге он накинуть сверх призового миллиона ещё $200 тысяч, если окажется, что доказательство Деолаликара верно.
На днях Аронсон, однако, привёл восемь аргументов, благодаря которым он склоняется к мысли, что Деолаликар с задачей тысячелетия не справился. Справедливости ради надо отметить, что непосредственно к предмету относятся только четыре пункта – в частности, Аронсон отмечает, что Деолаликар не даёт объяснения, почему его доказательство не работает для определённых частных задач.
Остальные же претензии относятся к оформлению материала: Аронсон негодует, что статья не выдержана в классическом стиле и в ней нет даже краткого объяснения, почему новое доказательство таки смогло преодолеть барьеры, мешавшие научному сообществу решить задачу последние 40 лет.
Подобный обзор, впрочем, был дан в дополнительно опубликованном Деолаликаром синопсисе , но его Аронсон счёл невнятным: «Я ощущал себя так, будто читаю . Слова касались глаз и испарялись, не успевая осесть в мозге", – иронизирует математик.
События продолжают развиваться, а Деолаликар остро переживает свои «пять минут славы». Верно его доказательство или нет – вдохновляет сам феномен того, что при колоссальной сложности задачи не только тысячи людей подключились к обсуждению, но и само доказательство обрело мировую известность задолго до публикации.
Сейчас индиец готовит некий полный вариант статьи, которая отправится уже на рассмотрение в научный журнал. Объём текущей версии манускрипта, содержащей некоторые исправления, уже вырос до 121 страницы.
О новоявленном исследователе почти ничего не известно, кроме того, что он женат, растит двоих детей, а единственным его хобби помимо математики является религиозная практика индуизма. Текст статьи Деолаликар предварил пространной надписью на санскрите и её англоязычной расшифровкой – это трогательная благодарность всем членам его семьи вплоть до дедушки с бабушкой.
Любопытна также фраза «эта работа – часть моего Matru-Pitru Rin» (обычай отдачи долгов родителям или оправдание надежд предков) (фото Hewlett-Packard).
В заключение мы предлагаем вам посмотреть первоапрельское видео, в котором известный своей эксцентричностью (и самосборными оригами) профессор MIT Эрик Демэн (Eric Demaine) убедительно «доказывает» за пару минут, что P=NP.
написал
Iffan
•
14 лет назад
