2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 Опубликовано доказательство P!=NP
Сообщение09.08.2010, 11:04 
Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P != NP.

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

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение10.08.2010, 14:59 
Этого не может быть!

 
 
 
 P!=NP
Сообщение10.08.2010, 16:51 
Аватара пользователя
По крайней мере выглядит серьезно

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

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

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение10.08.2010, 17:42 
Ну что, теперь надо подавать на присуждение миллиона долларов. :D

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение10.08.2010, 17:46 
Аватара пользователя
Интересно, а сколько времени должно пройти, чтобы работу признали (если она действительно решает задачу)? Я думаю это будет идти весьма долго, может до года.

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение10.08.2010, 18:57 
Аватара пользователя
ShMaxG
Некоторые работы и через годы не признают. А так обычно от 1 года. Проверка временем найдут ли ошибки или нет. Дальше считается что работа проверена. Но для разных премий есть разные условия. Может быть там 5 или 10 лет должно пройти.

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение10.08.2010, 18:58 
Аватара пользователя
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

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение10.08.2010, 21:24 
Аватара пользователя
Circiter в сообщении #343572 писал(а):
Этого не может быть!


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

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение10.08.2010, 23:03 
Аватара пользователя
Обсуждение нескольких существенных моментов, на которых представленное доказательство может провалиться:
http://rjlipton.wordpress.com/2010/08/0 ... 2%89%a0np/

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

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

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

2ArtemKim
Цитата:
Я так надеялся, что классы равны

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

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

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

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение11.08.2010, 12:40 
Аватара пользователя
Dandan в сообщении #343741 писал(а):
нужно обязательно "алгоритм" дополнить понятием "память" и активно этим понятием оперировать. Ведь если у нас в компьютере бесконечная память, то теоретически могут существовать полностью всё покрывающие радужные таблицы. И тогда вообще все NP задачи могут быть решены за O(1).
Почитайте учебники, что ли.

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение11.08.2010, 14:03 
если есть что сказать - просветите, а не отсылайте непонятно куда

 
 
 
 Re: Опубликовано доказательство P!=NP
Сообщение11.08.2010, 14:54 
Аватара пользователя
Бесконечную таблицу нельзя впихнуть в алгоритм, поскольку алгоритм - это объект конечный. Кроме того, даже чтение входа занимает O(n), за O(1) распознаются только очень простые языки типа "пятый символ полученной на вход строки совпадает с седьмым".

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

 
 
 [ Сообщений: 38 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group