четверг, августа 26, 2010

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

По предыдущему посту по поводу доказательства P ?= NP проблемы возникли вопросы, поэтому я решила написать еще один пост.

Первый вопрос, о чем вообще речь, что такое P ?= NP ?
Давайте я приведу пару ссылок на упрощенные описания проблемы.
Статья на lenta.ru
P vs. NP for Dummies
К сожалению, эти упрощенные описания настолько упрощены, что на практике они бесполезны. Вы - программисты, ребята умные, поэтому почитайте что-нибудь посерьезнее, например.
Lecture 6: P, NP, and Friends
Complexity theory статья в Википедии, далее следуйте по ссылкам.
Книга Пападимитриу, Стайглица "Комбинаторная оптимизация". Классическая книга, рекомендуется студентам, которые изучают теорию сложности.

Курс лекций по теории сложности обычно читается в вузах студентам, изучающим computer science. Все мои познания по этой теме как раз из курса, который я слушала на ВМиК МГУ. Я не могу сказать, что без этих знаний жить никак нельзя, но как минимум они дадут вам дополнительные очки при прохождении собеседований в компании с уютными офисами из стали и стекла, с названиями, выложенными разноцветными буковками.

Вопрос номер два: а как там дела с проверкой доказательства?
Несмотря на то, что окончательные выводы не сделаны, все говорит о том, что доказательство не верно. Деолаликар, правда, обещает исправить все замечания, но то, что он сможет это сделать, вызвает большие сомнения.

Страничка в формате wiki, посвященная доказательству Deolalikar P vs NP paper. Страница постоянно обновляется, так что самую свежую информацию следует искать здесь.

A Tale of A Serious Attempt At P≠NP Ричард Липтон подробно рассказывает о том, а что вообще это было.

Eight Signs A Claimed P≠NP Proof Is Wrong

воскресенье, августа 15, 2010

Буду выступать на ADD-2010

Конференция ADD-2010 - это конференция разработчиков ПО за вменяемые деньги. Проходит 23-24 сентября, в Ярославле, сейчас стоит 6000 рублей (вместе с обедом, но без проживания).

Меня туда позвал Стас Фомин, надо было только определиться с темой. В процессе раздумий и общения в Твиттере родилось две темы: "C++0x" и "Искусственный интеллект в играх". Надо было выбрать одну из них и тут Стас предложил гениальную идею - а зачем выбирать? Итого: я буду читать два доклада.

C++0x

Доклад о разработке нового стандарта языка С++. Чего хотели добиться, чего получилось, от чего пришлось отказаться.
Разработчики компиляторов не стали дожидаться выхода стандарта и уже много чего реализовали. Поэтому есть уже такие возможности С++0х, которые можно использовать прямо сейчас. О некоторых наиболее интересных возможностях будет рассказано. В основном речь будет вестись о GCC и MSVC++.

Искусственный интеллект в играх
Доклад ориентирован на тех, кто вообще никогда не занимался ИИ в играх и хочет получить об этой области общее представление. Будет рассказано о задачах, которые стоят перед программистом ИИ в играх. О вечном споре с теоретиками по поводу нейронных сетей, об алгоритмах поиска пути, о некоторых не очень честных приемах и о вполне честных, часто используемых подходах.

Все конференции разработчиков, про которые мне известно, в итоге вырождались в какой-то унылый междусобойчик, где одни и те же люди, рассказывают всё одно и то же по энному разу, при этом навязчиво рекламируя свои продукты и себя любимых. Очень хочется, чтобы ADD-2010 была не такой. Я со своей стороны сделаю все возможное, чтобы она была интересна разработчикам, а там посмотрим что получится. В любом случае, попытка достойна уважения.

Цена билетов, которая действует на настоящий момент - 6000 рублей. Это сильно дешевле, чем аналогичные московские конференции. Я слышала цену в 15000 на какую-то конференцию, совершенно негуманные цифры. Но все равно дороговато, на мой взгляд.
Проходит ADD-2010 в Ярославле. Оно и понятно, в Москве, насколько я слышала от организаторов других конференций, львиную долю от стоимости билета составляет аренда помещения. Я с удивлением обнаружила, что Ярославль находится недалеко от Москвы. На электричке до него ехать часа четыре, на машине можно и быстрее добраться. В Ярославле в этом году юбилей города, настроение праздничное. Короче, отличный повод выбраться из Москвы и увидеть памятник Ярославу Мудрому не только на тысячерублевке :-).

Мы, как говорится, работаем для вас, поэтому если уже сейчас есть какие-то вопросы или пожелания по моим докладам - пишите комментарии!

P.S. Стас пишет, что если зарегистрироваться со ссылкой на меня, то можно получить 5% скидку. Для этого надо указать промо код alenacpp.

вторник, августа 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 - результаты первой проверки. Есть несколько замечаний по доказательству, но это именно замечания, они не означают, что доказательство неправильное.

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

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