Holy fucking shit! (P \neq NP)

[yvl]

Похоже, мы станем свидетелями огромного прорыва человеческой мысли. По сообществу поползло докзательство разделения классов сложности P и NP. Эта задача является ключевой в теории вычислительных систем и математике вообще и находится в числе задач тысячелетия. По моему мнению она далеко опережает все остальные задачи по их практическим последствиям

Comments

[kolokolca]

Переслала доказательство на gmail -- сама ещё посмотреть не успела. С нетерпением жду реакции столпов! ;-)

[yvl]

Я копию получил через Сиа 3 часа назад уже. :) А ты, небось, раньше всех получила. :)Я просмотрел текст (по побочной диагонали), эклектично очень, "я его себе совсем другим представлял" (с). А зачем тебе столпов ждать, там вроде даже для меня все доступно?

[kolokolca]

Методы похожи на правду -- он использует distributions, solutions space geometry и локальность вычислений... Мы сейчас пытаемся понять где его аргумент ломается если заменить k-SAT на XORSAT.

[n0mad_0]

а можно нам тоже почитать? =) был бы очень благодарен!

eugene.kharitonov [пёс] gmail.com

[mentbuster]

А можно примитивное объяснение, для гуманитариев? В чем суть проблемы и к чему приведет ее решение?

[yvl]

Наверное здесь про проблему: http://web.mit.edu/newsoffice/2009/explainer-pnp.html

К чему приведет решение - если это доказательство правильное, то будем жить как прежде, но с уверенностью в завтрашнем дне :) Вкратце - криптография современная не будет даже под теоретической угрозой, с другой стороны - надежды на эффективное (быстрое) решение многих важных задач канут в лету.

[yvl]

Я поправлюсь, "не будет под теоретической угрозой, которую я считаю насколько-нибудь серьезной". (В деда мороза и квантовые компьютеры в обозримом будущем я не верю).

[yvl]

У меня лично - реакцией Стивена Кука и моих коллег-теоретиков. (Если Вы нашли ошибку в доказательстве - поделитесь, не томите :) )

[kolokolca]

Ну, это не аргумент -- он послал этот емайл торонтовской группе теории (хотя там в списках все прошлые аспиранты вроде меня, постдоки и visitors, так что много народа), чтобы ещё кто-нибудь посмотрел на доказательство. Он так делал и раньше, с другими неочевидно-неправильными доказательствами. То что емайл разлетелся дальше не его вина... Методы выглядят резонными, но проверить надо.

Возможная ошибка которую я сейчас пытаюсь проверить это насколько автор учитывает роль порядка в FO(LFP) когда он смотрит на распределение и структуру solution space получаемых из FO(LFP) алгоритма. На неупорядочных структурах FO(LFP) не соответствует P, в частности, в этой логике нельзя выразить то что система уравнений над GF2 (0 и 1, 1+1=0) имеет решение...

Автор там вводит новые relations вместо порядка, утверждая что это technicality (p. 67) -- но получает order-invariant logic, для которой насколько я знаю не известно что она captures P... Может оно и работает, но там может быть и ошибка, надо разбираться.

[yvl]

Я протрезвею и тоже посмотрю (если успею, гггг) :)

[kolokolca]

Кстати, сообщение о доказательстве появилось в одном из блогов теоретиков -- у Ричарда Липтона в http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/

Липтон пишет что сам ещё не проверял, просто что оно появилось и выглядит так-то. Если появится подтверждение или опровержение, то скорее всего оно будет в комментариях к этому посту. Так что следите за RSS feed'ом ;-)

Вопрос народу в теме -- как же он все-таки избегает relativization barrier? А я пока перечитываю учебник по конечной теории моделей (Либкина) и пытаюсь понять как Deolalikar использует порядок в своем доказательстве.

[girly_girl_]

а вот еще одно мнение, тоже в блоге у теоретика:
http://scottaaronson.com/blog/?p=456

[kolokolca]

О, Скотт проснулся ;-)

И у него в комментариях уже FMTшники выразили свое недоверие к использованию порядка в FO(LFP) в доказательстве.

То же самое говорит Баррингтон в блоге у Липтона.

[kolokolca]

Deolalikar только что запостил новую версию: http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf

Сейчас буду смотреть.

[yvl]

"Ссылку в студию!" (с)