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

kolokolca — 11.08.2010 И вот уже многие из моих немногих френдов пишут о возможном доказательстве P != 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 большой, ему видней" ;-)  

Оставить комментарий

Популярные посты:

• Архив