По предыдущему посту по поводу доказательства 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
Нет - и не надо.
ОтветитьУдалитьВидео лекция про теме, в достаточно популярной форме, с картинками:
ОтветитьУдалитьhttp://video.ias.edu/P-vs-NP
Я наконец-то вник в суть вопроса, читая лекцию Ааронсона.
ОтветитьУдалитьКомбинаторная оптимизация и теория сложности -- это, вообще говоря, разные науки.
ОтветитьУдалитьКомбинаторная оптимизация -- это, грубо говоря, верхние оценки (теория "простоты").
А теория сложности -- нижние.
И лично я бы не рекомендовал Papadimitriou.
ilyaraz:
ОтветитьУдалитьИ лично я бы не рекомендовал Papadimitriou.
А что бы рекомендовали?
Хоть и говорят, что нет ничего практичнее хорошей теории, но детали этой темы не так существенны для программистов, как для теоретиков, разработчиков компьютерных алгоритмов.
ОтветитьУдалитьУ Кормена вроде как годный материал по этой теме, целая глава.
ОтветитьУдалитьhttp://books.google.ru/books?id=NLngYyWFl_YC&lpg=PP1&dq=cormen&pg=PA966#v=onepage&q&f=false
А так, если, конечно, у него таки получится доказать, нужно будет и в стат. физику, и в теорию сложности с головой, иначе не пустят на программистские тусовки
будущего:)
Теория сложности -- книжки Сипсера и Ароры-Барака.
ОтветитьУдалитьКомбинаторная оптимизация -- базовая есть в Кормене. Хочется большего -- Скрайвер.
Я вот не пойму, в каком месте эта задача тысячелетия? Разве ответ даст что-то полезное )
ОтветитьУдалить@Александр.
ОтветитьУдалитьСмотря какой будет ответ ))