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 - результаты первой проверки. Есть несколько замечаний по доказательству, но это именно замечания, они не означают, что доказательство неправильное.
Откровенно неправильные доказательства этой проблемы предлагаются довольно часто. Но это доказательство сильно отличается от многочисленных жалких попыток. Как говорят математики, оно "выглядит серьезно". Даже если оно неправильное, то там высказано несколько интересных идей, которые могут привести к правильному доказательству. Например, народ отмечает использование статистической физики. То есть это как минимум достойная попытка.
Проверка правильности продолжается и будет продолжаться еще долго, я думаю. Будет интересно почитать мнение русскоязычных математиков, специалистов по теории сложности, киньте ссылку, если у кого есть.
Ух, если ему это удалось, буду ходить по Питеру с плакатом "P != NP" и всячески его восхвалять.
ОтветитьУдалитьВы бы лучше вкратце пояснили, чем P отличается от NP, и какие бонусы сулит их неравенство.
ОтветитьУдалитьЯ вот сколько википедию не читал, так и не понял, чем урадоваться в этом доказательстве.
Тоесть если бы доказали обратное, вроде как можно и радоваться. А неравенство не дает в руки никаких новых карт.
насколько я понял, доказательство данного факта спасает нас от страха, что в одни прекрасный день рухнет вся защита, построенная на криптографии
ОтветитьУдалитьДоказательство данного факта оставляет рабочие места специалистам по оптимизации и алгоритмам.
ОтветитьУдалитьЧтобы доказать P==NP, необходимо дать P-алгоритм для какой-нибудь NP задачи.
Для всех остальных существуют редукции - то есть автоматизируемые трансформации. И это сразу решает огромное количество алгоритмов.
А вот факт P!=NP приводит к тому, что можно до бесконечности заниматься решением "локальных задач" типа полиномиальное решение SAT удовлетворяющего особым условиям. А эти особые условия встречаются в каких-то прикладных задачах.
позволяет позволяет бесконечный поток улучшения а
Этот комментарий был удален автором.
ОтветитьУдалить@Дмитрий, Вы говорите бред. Факторизация чисел не относится к классу NP. И даже если бы относилась, то из равенства никак не следовало существование алгоритма сравнимого по сложности с умножением.
ОтветитьУдалить@Анонимный:
ОтветитьУдалитьДа, я напутал. Комментарий удалю, чтобы никого не вводить в заблуждение.
Интересно было бы посмотреть, как именно он применяет статфизику. ИМХО, статфизика — это теория вероятностей плюс постулаты (термодинамики etc), так что теорвера хватило бы за глаза.
ОтветитьУдалитьДарк
ОтветитьУдалитьВы бы лучше вкратце пояснили, чем 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 главе, но ее-то он пока еще не прочитал.
Как ни странно, но здесь:
ОтветитьУдалить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
уже считают проблему решенной
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