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

67
задан 9 revs, 5 users 50% 13 April 2017 в 14:17
поделиться

7 ответов

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

Со стр. 86 газеты.

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

В других частях статьи показано, что некоторые проблемы NP не могут быть разбиты таким образом. Таким образом, NP / = P

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

57
ответ дан 24 November 2019 в 14:43
поделиться

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

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

16
ответ дан 24 November 2019 в 14:43
поделиться

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

5
ответ дан 24 November 2019 в 14:43
поделиться

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

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

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

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

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

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

9
ответ дан 24 November 2019 в 14:43
поделиться

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

3
ответ дан 24 November 2019 в 14:43
поделиться

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

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

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

-4
ответ дан 24 November 2019 в 14:43
поделиться

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

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

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

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

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

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

1
ответ дан 24 November 2019 в 14:43
поделиться
Другие вопросы по тегам:

Похожие вопросы: