Опубликовано доказательство P!=NP

[Dandan]

Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P != NP.

Само док-во: http://www.win.tue.nl/~gwoegi/P-versus- ... alikar.pdf

[Circiter]

Этого не может быть!

[ArtemKim]

По крайней мере выглядит серьезно

http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

Темы объединены.

[Rasool]

Ну что, теперь надо подавать на присуждение миллиона долларов.

[ShMaxG]

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

[Pavia]

ShMaxG
Некоторые работы и через годы не признают. А так обычно от 1 года. Проверка временем найдут ли ошибки или нет. Дальше считается что работа проверена. Но для разных премий есть разные условия. Может быть там 5 или 10 лет должно пройти.

[maxal]

ShMaxG в сообщении #343598 писал(а):

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

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

Before consideration, a proposed solution must be published in a refereed mathematics publication of worldwide repute (or such other form as the SAB shall determine qualifies), and it must also have general acceptance in the mathematics community two years after. Following this two-year waiting period, the SAB will decide whether a solution merits detailed consideration.

Кстати, автор обновил доказательство на своей страничке:
http://www.hpl.hp.com/personal/Vinay_De ... ed-mjr.pdf

-- Tue Aug 10, 2010 11:43:45 --

Вики-страничка, на которой ведется анализ доказательства:
http://michaelnielsen.org/polymath1/ind ... 3DNP_paper

[ArtemKim]

Circiter в сообщении #343572 писал(а):

Этого не может быть!

Я так надеялся, что классы равны

[maxal]

Обсуждение нескольких существенных моментов, на которых представленное доказательство может провалиться:
http://rjlipton.wordpress.com/2010/08/0 ... 2%89%a0np/

[Circiter]

Поделюсь впечатлениями. Я уже третий раз поверхностно перечитываю стостраничный препринт этого индуса и все-равно не понял абсолютно ничего. :) Частично схема доказательства для меня начинает проясняться только по-мере прочтения многочисленных обсуждений этой работы. Да, в теории сложности и примыкающих областях я полный "ламер", но мне кажется, что даже для специалистов, буквально "живущих" проблемой $\mathrm{P}\neq\mathrm{NP}$, вникнуть в идеи автора будет весьма не просто; а значит, общественная тех. экспертиза работы может затянуться на очень длительный срок, если только, конечно, кто-нибудь в ближайшее время не найдет какой-нибудь фатальный ляп в доказательстве. Но пока никаких серьезных огрехов вроде-бы никто не смог обнаружить, за исключением мелких (хотя и представленных в изобилии) оговорок, опечаток и неточностей.

Лично мне очень понравился весь его фреймворк на основе неподвижных точек. Но, наверное, это потому, что сей момент является единственной вещью, которая до меня хоть как-то дошла. :)

Также интересен подход виновника ажиотажа к обнародованию безусловно весомой рукописи. Не, точно под Перельмана косит, однозначно. :)

2ArtemKim

Цитата:

Я так надеялся, что классы равны

И не вы один. На это вся computer science надеялась. :) Представляете, какой философский "пригруз" несет с собой факт неравенства этих классов?

А может быть все это суть происки влиятельных структур, стремящихся "заболтать" потенциальные уязвимости некоторых, например, криптографических подходов? Ой, как страшно-то... :)

[Dandan]

Не знаю и врядле пойму как он это доказал, но я думал, что для доказательства такого факта нужно обязательно "алгоритм" дополнить понятием "память" и активно этим понятием оперировать. Ведь если у нас в компьютере бесконечная память, то теоретически могут существовать полностью всё покрывающие радужные таблицы. И тогда вообще все NP задачи могут быть решены за O(1).

[Xaositect]

Dandan в сообщении #343741 писал(а):

нужно обязательно "алгоритм" дополнить понятием "память" и активно этим понятием оперировать. Ведь если у нас в компьютере бесконечная память, то теоретически могут существовать полностью всё покрывающие радужные таблицы. И тогда вообще все NP задачи могут быть решены за O(1).

Почитайте учебники, что ли.

[Dandan]

если есть что сказать - просветите, а не отсылайте непонятно куда

[Xaositect]

Бесконечную таблицу нельзя впихнуть в алгоритм, поскольку алгоритм - это объект конечный. Кроме того, даже чтение входа занимает O(n), за O(1) распознаются только очень простые языки типа "пятый символ полученной на вход строки совпадает с седьмым".

[Dandan]

Ну стандартное определение алгоритма конечно, никто не спорит. Я просто привел нестрогий аргумент того, что нужно учитывать "размер" алгоритма.
Можно еще так сказать. Вот есть у вас какой-то алгоритм. Вы можете просчитать некоторые значения и составить другой алгоритм с таблицей, в которой сохранены подсчитанные значения. Он будет больше по "размеру", но будет работать в общем быстрее (все-таки O(1) на закешированных значения, если не учитывать считывание входа и запись выхода). Конечно, в пределе эти алгоритмы будут одинаковы, но факт более быстрого подсчета некоторых значений остается.