Объясните доказательство Винай Деолиликара о том, что P!= NP

Ответ 1

Я просмотрел только бумагу, но вот краткий обзор того, как все это происходит вместе.

Со страницы 86 документа.

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

Другие части статьи показывают, что некоторые проблемы NP не могут быть разбиты таким образом. Таким образом, NP/= P

В значительной части статьи проводится определение условной независимости и доказательство этих двух точек.

Ответ 2

У Dick Lipton есть приятная запись статьи о бумаге и первые впечатления от нее. К сожалению, он также является техническим. Из того, что я могу понять, основной инновацией Deolalikar, похоже, является использование некоторых концепций из статистической физики и теории конечных моделей и привязка их к проблеме.

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

Ответ 3

Мне это понравилось (http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html):

Его аргумент вращается вокруг конкретной задачи - булевой проблемы выполнимости, которая задает вопрос о том, может ли совокупность логических операторов быть одновременно истинным или противоречить друг другу. Это, как известно, проблема NP.

Deolalikar утверждает, что показал, что нет программы, которая может завершить это быстро с нуля, и что это поэтому не является проблемой P. Его аргумент предполагает гениальное использование статистической физики, поскольку он использует математическая структура, которая следует многие из тех же правил, что и случайные физической системы.

Эффекты вышеизложенного могут быть весьма значительными:

Если результат будет, это докажет что два класса P и NP не являются идентичны и налагают серьезные ограничения на какие компьютеры могут выполнить - подразумевая, что многие задачи могут быть в принципе, неприемлемо сложным.

Для некоторых проблем - в том числе факторизация - результат не четко сказать, можно ли их решить быстро. Но огромный подкласс проблемы, называемые "NP-complete", будут обречено. Известным примером является проблема коммивояжера - поиск кратчайший маршрут между набором города. Такие проблемы можно проверить быстро, но если P ≠ NP, то есть нет компьютерной программы, которая может завершить их быстро с нуля.

Ответ 4

Это мое понимание техники доказательства: он использует логику первого порядка, чтобы охарактеризовать все полиномиальные алгоритмы времени, а затем показывает, что для больших задач SAT с определенными свойствами нет, что алгоритм полиномиального времени может определить их выполнимость.

Ответ 5

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

Ответ 6

Такое доказательство должно охватывать все классы алгоритмов, такие как непрерывная глобальная оптимизация.

Например, в задаче 3-SAT мы должны оценивать переменные для выполнения всех альтернатив троек этих переменных или их отрицаний. Посмотрите, что x OR y можно изменить на оптимизацию

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

и аналогично семи членов для альтернативы трех переменных.

Нахождение глобального минимума суммы таких многочленов для всех членов позволило бы решить нашу проблему. (источник)

Он выходит из стандартных комбинаторных методов в непрерывный мир, используя методы_градиента, методы удаления локальных минимов, эволюционные алгоритмы. Это совершенно другое королевство - численный анализ - я не верю, что такое доказательство действительно могло бы покрыть (?)

Ответ 7

Стоит отметить, что с доказательствами "дьявол в деталях". Обзор высокого уровня, очевидно, выглядит примерно так:

Некоторые отношения между пунктами, показать, что это соотношение подразумевает X и что подразумевает Y, и поэтому мой аргумент показано на рисунке.

Я имею в виду, что это может быть через Induction или любую другую форму доказательства, но я говорю о высоком уровне обзора бесполезно. Нет смысла объяснять это. Хотя сам вопрос относится к информатике, его лучше всего оставлять математикам (считалось, что это невероятно интересно).