P vs. NP: суета вокруг дивана.

В субботу Стив Кук послал емайл группе теории Торонтовского универа (включающей бывших аспирантов) мол посмотрите на такое-то доказательство, вроде не полный бред. Он подобные доказательства получает регулярно, и если не может сразу найти ошибку то дает почитать аспирантам и/или спрашивает у народа. Так было и с доказательством Deolalikar'а -- оно использует результаты из конечной теории моделей и из статистической физики, в которых Стив не специалист. На первый взгляд статья выглядит серьезной, хорошо и читабельно написана, упоминает результаты из нескольких областей математики и теор. кибернетики, которые в принципе могли бы привести к чему-то новому.
Через пару часов один бывший студент SFU (одного из Ванкуверских универов) который сейчас в Торонто переслал этот емайл всему факультету computer science в SFU -- мол, ура, P != NP доказано, сам Стив Кук это сказал. Один SFUшный профессор написал об этом в своем блоге; оттуда информация попала в slashdot... И понеслось.
Ричард Липтон, (кстати недавно писавший в своем блоге что будет если непрофесионал докажет P != NP) написал что появилось правдоподобное доказательство. Я не знаю есть ли причинно-следственная связь между его постом и тем, что сообщение (а вскоре и статья) ушли в сеть через SFU.... На следующий день о доказательстве (гораздо менее оптимистично) написали другие теоретики...
Ошибки нашли довольно быстро (товарищ пытается использовать результаты конечной теории моделей опуская очень важную деталь) -- ещё в воскресенье об этом говорили в комментариях к блогу Скотта Ааронсона. Я писала об этом Стиву -- он ответил "да знаю уже" ;-) Но тем не менее, если верить Липтону, группа талантливейших математиков (правда не занимающихся конечной теорией моделей) пытается понять можно ли из этой статьи хоть что-нибудь спасти.
Лично мне кажется что минимум одна ошибка (некорректное использование теоремы Иммермана-Варди) в этой статье не чинибельна, люди в этой области много лет пытались использовать те методы анализа о которых пишет Deolalikar для случая логик с порядком и показали что эти методы не работают. Но, может быть, если починить другие ошибки, там и можно будет доказать что-нибудь интересное про распределение решений в задачах типа Constraint Satisfaction, выразимых в логике FO(LFP). Подождем, посмотрим.
Во всей этой ситуации мне жалко автора, Deolalikar'а. С одной стороны, правда, он получил поддержку и помощь лучших математиков и теоретиков (таких как Terrence Tao и Timothy Gowers). С другой стороны неприятно когда посылаешь статью нескольким экспертам -- и уже через несколько часов вся сетка обсуждает ошибки в статье, создавая понятно какую репутацию. Но тут уж "виновен не жираф/ а тот кто крикнул из ветвей/ Steve Cook большой, ему видней" ;-)
|
</> |