вторник, августа 10, 2010

P != NP, доказательство Виная Деолаликара

Updated 26.08.2010: Доказательство Деолаликара скорее всего неправильное

6 августа Винай Деолаликар (Vinay Deolalikar) разослал доказательство одной из проблем тысячелетия, которая близка программистам. Это доказательство того, что P != NP. Осталось убедиться в том, что это доказательство верно.

Вот само доказательство: P != NP (Ахтунг! 100 страниц математических формул)

Я поискала в Интернете отзывы математиков и не математиков, вот чего нашла.

Первое упоминание этого доказательства в открытых источниках.

Веселое обсуждение на слэшдоте.

За доказательство проблемы тысячелетия дают миллион долларов. Скотт Ааронсон накинул еще 200 тысяч.

Математик Ричард Липтон опубликовал у себя в блоге две статьи
A Proof That P Is Not Equal To NP?
Issues In The Proof That P≠NP - результаты первой проверки. Есть несколько замечаний по доказательству, но это именно замечания, они не означают, что доказательство неправильное.

Откровенно неправильные доказательства этой проблемы предлагаются довольно часто. Но это доказательство сильно отличается от многочисленных жалких попыток. Как говорят математики, оно "выглядит серьезно". Даже если оно неправильное, то там высказано несколько интересных идей, которые могут привести к правильному доказательству. Например, народ отмечает использование статистической физики. То есть это как минимум достойная попытка.

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

17 коммент.:

Саша комментирует...

Ух, если ему это удалось, буду ходить по Питеру с плакатом "P != NP" и всячески его восхвалять.

Дарк комментирует...

Вы бы лучше вкратце пояснили, чем P отличается от NP, и какие бонусы сулит их неравенство.
Я вот сколько википедию не читал, так и не понял, чем урадоваться в этом доказательстве.
Тоесть если бы доказали обратное, вроде как можно и радоваться. А неравенство не дает в руки никаких новых карт.

Анонимный комментирует...

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

Анонимный комментирует...

Доказательство данного факта оставляет рабочие места специалистам по оптимизации и алгоритмам.
Чтобы доказать P==NP, необходимо дать P-алгоритм для какой-нибудь NP задачи.
Для всех остальных существуют редукции - то есть автоматизируемые трансформации. И это сразу решает огромное количество алгоритмов.
А вот факт P!=NP приводит к тому, что можно до бесконечности заниматься решением "локальных задач" типа полиномиальное решение SAT удовлетворяющего особым условиям. А эти особые условия встречаются в каких-то прикладных задачах.
позволяет позволяет бесконечный поток улучшения а

Дмитрий Scriptin комментирует...
Этот комментарий был удален автором.
Анонимный комментирует...

@Дмитрий, Вы говорите бред. Факторизация чисел не относится к классу NP. И даже если бы относилась, то из равенства никак не следовало существование алгоритма сравнимого по сложности с умножением.

Дмитрий Scriptin комментирует...

@Анонимный:
Да, я напутал. Комментарий удалю, чтобы никого не вводить в заблуждение.

Анонимный комментирует...

Интересно было бы посмотреть, как именно он применяет статфизику. ИМХО, статфизика — это теория вероятностей плюс постулаты (термодинамики etc), так что теорвера хватило бы за глаза.

Alena комментирует...

Дарк
Вы бы лучше вкратце пояснили, чем P отличается от NP, и какие бонусы сулит их неравенство.

Не получается вкратце. Сейчас журналисты пытаются это сделать, получается плохо, но у них выбора другого нет.

Тут надо либо более-менее серьезно знакомиться с теорией сложности. Либо просто порадоваться за математиков, которые решили или почти решили одну из задач тысячелетия.

Я вот сколько википедию не читал, так и не понял, чем урадоваться в этом доказательстве.
Тоесть если бы доказали обратное, вроде как можно и радоваться. А неравенство не дает в руки никаких новых карт.


Как уже ответили выше, не надо выбрасывать на помойку всю криптографию. И это хорошо.

Анонимный комментирует...

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

Анонимный комментирует...

Я не специалист, но по-моему интересно будет следить за страницей Deolalikar's P!=NP paper
Там собирается разнообразная информация на тему (правда, на английском).
Особенно порадовала ссылка A nice introductory Q&A page on Deolalikar's proof, by Eric Stansifer с неформальным введением в доказательство Деолаликара. Автор пишет, что первые 6 глав работы выглядят достаточно убедительно, а самое интересное (основное доказательство) происходит в 7 главе, но ее-то он пока еще не прочитал.

Dmitry Shiryaev комментирует...

Как ни странно, но здесь:

http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D1%8B_%D1%82%D1%8B%D1%81%D1%8F%D1%87%D0%B5%D0%BB%D0%B5%D1%82%D0%B8%D1%8F

уже считают проблему решенной

Alena комментирует...

Dmitry Shiryaev
Как ни странно, но здесь:

http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D1%8B_%D1%82%D1%8B%D1%81%D1%8F%D1%87%D0%B5%D0%BB%D0%B5%D1%82%D0%B8%D1%8F

уже считают проблему решенной


Оптимистичные ребята. Но там уже все обратно исправили.

Анонимный комментирует...

You were visited with excellent idea

Анонимный комментирует...

К сожалению, нашлось несколько ошибок, которые, судя по оценкам Теренса Тао, являются непоправимыми. Однако, уже сейчас Тао и группой математиков такого же уровня предложен ряд задач (не P!=NP, конечно, но все равно прорывов в современной теории вычислений), для решения которых можно использовать стат физический подход Виная.

Подробности - в блоге Дика Липмана (кто, на самом деле и организовал этот "отряд проверки" из Тао и Со):
http://rjlipton.wordpress.com/

Анонимный комментирует...

Ну вот, вроде как опровергли, хотя шансы все еще имеются.

Анонимный комментирует...

Алена! а что Вы думаете по этому поводу? Тоже претендент на решение.

http://meta.kz/interesnie-fakti/861481-armyanskiy-programmist-reshil-zadachu-kotoraya-delaet-bessmyslennymi-k.html