Индиец попробовал на вкус задачу тысячелетия
Математические блоги шумят как улей: никому не узнаваемый сотрудник лаборатории Hewlett-Packard в Пало-Альто, индиец по национальности, опубликовал огромную статью, претендующую на решение одной из основных открытых неприятностей математики. К настоящему моменту в контролируемом всем миром доказательстве уже нашли неточности, в нахождении которых кроме этого нашли неточности, в которых… В общем – нужно разобраться, что же случилось.
Предыстория такова. В субботу 7 августа небезызвестный математик Стив Кук (Stephen Arthur Cook) послал по email сотрудникам из университета Торонто (UT) и некоторым своим бывшим аспирантам PDF-файл, пришедший к нему чуть ранее. Тем самым он завёл часовой механизм бомбы, которой было суждено «взорвать» математический мир.
В 116-страничном документе предлагался уникальный комплексный метод ответа задачи о равенстве классов P и NP, в первой половине 70-ых годов двадцатого века Куком и сформулированной.
В чём же сущность фразы «классы сложности P и NP не равны»? В случае если сказать совсем грубо, то P – это класс задач, каковые мы можем скоро решать, а NP – класс задач, у которых мы скоро можем контролировать правильность ответа. Либо несложнее и в вопросительной форме: в случае если имеющееся хорошее ответ задачи возможно скоро проверить, возможно ли его столь же скоро отыскать? (иллюстрация amazon.com/Appalachian State University/MIT)
Представшее взгляду Стивена подтверждение разительно отличалось от других уже по уровню аргументации. Явных неточностей в работе человека по имени Винэй Деолаликар (Vinay Deolalikar) математик сходу не отыскал и передал бумагу для проверки «второму эшелону». (По-видимому, он решил очень не зарываться, потому, что привлечённая автором конечная теория моделей не входила в сферу компетенции Кука.)
Потом события развивались с завидной скоростью. Один из аспирантов переслал письмо сходу всему факультету информатики ванкуверского отделения университета Саймона Фрейзера (SFU) с комментарием в духе «Одобрено самим Стивом Куком». Практически сразу же информация попала на портал Slashdot, а на следующий сутки математик Грэг Бэйкер (Grag Baker) кроме этого выложил в собственном блоге посланную ему копию доказательства.
В следствии уже к началу семь дней целый Интернет был в курсе событий. Из-за масштабности замаха, что сделал Деолаликар, новость о его доказательстве достаточно скоро попала и на страницы ведущих новостных научных сайтов и агентств – от BBC до Nature.
Создатель окончательной формулировки задачи, лауреат премии Тьюринга Стив Кук. Тут возможно просмотреть его презентацию о важности вопроса равенства P и NP (фото University of Toronto).
Обстоятельство шумихи несложна. Эта математическая неприятность входит в перечень семи задач тысячелетия (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 лет.
О новоявленном исследователе практически ничего не известно, помимо этого, что он женат, растит двоих детей, а единственным его хобби кроме математики есть религиозная практика индуизма. Текст статьи Деолаликар предварил пространной надписью на санскрите и её английской расшифровкой – это милая признательность всем участникам его семьи впредь до дедушки с бабушкой.Любопытна кроме этого фраза «эта работа – часть моего Matru-Pitru Rin» (обычай отдачи долгов родителям либо оправдание надежд предков) (фото Hewlett-Packard).
Подобный обзор, но, был дан в дополнительно опубликованном Деолаликаром синопсисе (PDF-документ), но его Аронсон счёл невнятным: «Я чувствовал себя так, словно бы просматриваю »Сердце тьмы Конрада. Слова касались глаз и испарялись, не успевая осесть в мозге, – иронизирует математик.
События развиваются , а Деолаликар остро переживает собственные «пять мин. славы». Правильно его подтверждение либо нет – воодушевляет сам феномен того, что при большой сложности задачи не только тысячи людей подключились к дискуссии, но и само подтверждение получило мировую известность задолго до публикации.
на данный момент индиец готовит некоторый полный вариант статьи, которая отправится уже на рассмотрение в научный издание. Количество текущей версии манускрипта, содержащей кое-какие исправления, уже вырос до 121 страницы.
Напоследок мы предлагаем вам взглянуть первоапрельское видео, в котором известный своей эксцентричностью (и самосборными оригами) доктор наук MIT Эрик Демэн (Eric Demaine) убедительно «обосновывает» за несколько мин., что P=NP.
