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

топ 100 блогов kolokolca11.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 большой, ему видней" ;-)  

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

Архив записей в блогах:
Прошла городская игра по ВтМ. Прекрасные были выходные, мне очень понравилось. Мне очень не хотелось играть вампира, так что я упорно пыталась заявиться на игру Охотником или Магом. Увы, Охотники были только игротехническими, Магов не было, но, ...
Самый мой нелюбимый город России - это Москва. Но, тем не менее, волею судьбы приходится туда приезжать в среднем два раза в месяц по делам. Как бы я хотела, чтобы все эти дела делались не через Москву. Обычно в Москве я оказываюсь из-за того что мне надо на самолет, то есть основной мо ...
Послал фоточки дорогому начальству. Пусть решают что-то. Осталось 2-3 дня, но гикнуться можно и за 2-3 минуты. Это ещё надо учесть, что я весь день таблетки ем и корвалолом запиваю. ...
Трофейный немецкий танк Pz.IV, отремонтированный на Сталинградской судоверфи, перед передачей частям Красной армии; ~ зима 1942-1943-го гг. ...
Быть молодым в России не только тяжело, но и абсолютно бесперспективно. Причём, во всех сферах жизни. Начну с досуга: программы всех центральных телеканалов ориентированы на аудиторию, которой далеко за 40. Там есть множество передач, которые вызывают живой интерес у домохозяек и граждан ...