четверг, августа 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

10 коммент.:

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

Нет - и не надо.

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

Видео лекция про теме, в достаточно популярной форме, с картинками:

http://video.ias.edu/P-vs-NP

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

Я наконец-то вник в суть вопроса, читая лекцию Ааронсона.

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

Комбинаторная оптимизация и теория сложности -- это, вообще говоря, разные науки.

Комбинаторная оптимизация -- это, грубо говоря, верхние оценки (теория "простоты").

А теория сложности -- нижние.

И лично я бы не рекомендовал Papadimitriou.

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

ilyaraz:

И лично я бы не рекомендовал Papadimitriou.

А что бы рекомендовали?

Peter Nikouline комментирует...

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

pure virtual комментирует...

У Кормена вроде как годный материал по этой теме, целая глава.
http://books.google.ru/books?id=NLngYyWFl_YC&lpg=PP1&dq=cormen&pg=PA966#v=onepage&q&f=false

А так, если, конечно, у него таки получится доказать, нужно будет и в стат. физику, и в теорию сложности с головой, иначе не пустят на программистские тусовки
будущего:)

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

Теория сложности -- книжки Сипсера и Ароры-Барака.

Комбинаторная оптимизация -- базовая есть в Кормене. Хочется большего -- Скрайвер.

Александр комментирует...

Я вот не пойму, в каком месте эта задача тысячелетия? Разве ответ даст что-то полезное )

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

@Александр.

Смотря какой будет ответ ))