Объясните доказательство Vinay Deolalikar, что P!= NP
7 ответов
Я только отсканировал бумагу, но вот краткое изложение того, как все это сочетается.
Со страницы 86 статьи.
... алгоритмы полиномиального времени преуспевают, последовательно "разбивая" проблему на более мелкие подзадачи, которые соединяются друг с другом посредством условной независимости. Следовательно, алгоритмы полиномиального времени не могут решать проблемы в режимах, где блоки, порядок которых совпадает с базовым экземпляром задачи, требуют одновременного разрешения.
Другие части документа показывают, что некоторые проблемы NP не могут быть разбиты таким образом. Таким образом, NP/= P
Большая часть работы посвящена определению условной независимости и доказательству этих двух пунктов.
У Дика Липтона есть хорошая запись в блоге о газете и его первых впечатлениях о ней. К сожалению, это также технический. Из того, что я могу понять, главным нововведением Деолаликара, кажется, является использование некоторых понятий из статистической физики и теории конечных моделей и привязка их к проблеме.
Я с Rex M с этим, некоторые результаты, в основном математические, не могут быть выражены людям, которые не имеют технического мастерства.
Мне понравилось это ( 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, то нет компьютерной программы, которая могла бы их быстро выполнить с нуля.
Это мое понимание техники доказательства: он использует логику первого порядка для характеристики всех алгоритмов полиномиального времени, а затем показывает, что для больших задач SAT с определенными свойствами ни один алгоритм полиномиального времени не может определить их выполнимость.
Еще один способ думать об этом, который может быть совершенно неправильным, но мое первое впечатление, когда я читаю его на первом проходе, состоит в том, что мы думаем о назначении / очистке терминов в удовлетворенности контурами как о формировании и разрушении кластеров "упорядоченных". структура ", и что он затем использует статистическую физику, чтобы показать, что в полиномиальных операциях недостаточно скорости для выполнения этих операций в определенном" фазовом пространстве "операций, потому что эти" кластеры "оказываются слишком далеко друг от друга.
Такое доказательство должно охватывать все классы алгоритмов, таких как непрерывная глобальная оптимизация.
Например, в задаче 3-SAT мы должны оценить переменные, чтобы выполнить все альтернативы троек этих переменных или их отрицаний. Посмотри что x OR y может быть изменен на оптимизацию
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
и аналогично семь членов для альтернативы трех переменных.
Нахождение глобального минимума суммы таких многочленов для всех членов решило бы нашу проблему. ( источник)
Он выходит из стандартных комбинаторных техник в непрерывный мир, используя методы _gradient, методы удаления локальных минимумов, эволюционные алгоритмы. Это совершенно другое царство - численный анализ - я не верю, что такое доказательство могло бы действительно покрыть (?)
Стоит отметить, что с доказательствами "дьявол кроется в деталях". Обзор высокого уровня, очевидно, что-то вроде:
Какие-то отношения между предметами показывают, что эти отношения подразумевают X, а это подразумевает Y, и, таким образом, мой аргумент показан.
Я имею в виду, что это может быть с помощью индукции или любой другой формы доказывания, но то, что я говорю, это обзор высокого уровня, который бесполезен. Нет смысла объяснять это. Хотя сам вопрос относится к информатике, его лучше оставить математикам (хотя он, безусловно, невероятно интересен).