Как не решить P = NP?

97

Существует множество попыток доказать либо либо , и, естественно, многие люди задумываются над этим вопросом, имея идеи для доказательства того или иного направления.PN Pпзнак равноNппNп

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

Мы хотим избежать исследования тупиков, так что же они?

Рафаэль
источник
16
Я думаю, что лучше быть вики сообщества (потому что нет уникального ответа на этот вопрос, он слишком широк).
6
@SaeedAmiri Нет. Вики сообщества раньше были алиби, чтобы разрешать вопросы, которые не подходили для платформы Stack Exchange, но это больше не делается .
Жиль
4
Примечание модератора: этот вопрос шире, чем обычный вопрос о стеке, но мы пытаемся создать каноническую пару вопросов и ответов. Если вы считаете, что этот вопрос не должен существовать в его нынешнем виде, пожалуйста, обсудите его на нашем мета-сайте .
Жиль
для аналогичного вопроса с противоположной / конструктивной стороны посмотрите, как могут быть решены теории и запросы по информатике?
vzn
4
Ответ вига: arXiv - кладезь способов не делать этого.
псевдоним

Ответы:

76

Я бы сказал, что наиболее известные барьеры для решения :пзнак равноNп

  1. Релятивизация (как упомянуто Ран Г.)
  2. Естественные доказательства - при определенных криптографических предположениях Рудич и Разборов доказали, что мы не можем доказать используя класс доказательств, называемых естественными доказательствами.PNP
  3. Алгебризация - Скотт Ааронсон и Ави Вигдерсон. Они доказывают, что доказательства, которые алгебрируют, не могут разделить иН ПпNп

Другой, с которым я знаком, это результат, что ни одна формулировка LP не может решить TSP (это было доказано Yannakakis для симметричных LP и совсем недавно распространено на общие LP). Вот сообщение в блоге, обсуждающее результат.

Опт
источник
4
Соответствующие ссылки: о барьерах вообще и игрушечных примерах . Кроме того, вы должны быть осторожны с вашим последним предложением, я думаю, что было бы целесообразно включить ссылку на пост в блоге, который объясняет, почему TSP, не достижимый в результате общего LP, не доказывает , так как люди могут быть смущены тот факт, что LP является полной. PпNпп
Артем Казнатчеев
1
Если вы хотите улучшить ответ (он еще не готов к принятию), добавьте короткие пояснения и ссылки на детали, чтобы любопытный читатель знал, о чем вы говорите.
Рафаэль
57

Примечание: я еще не проверил ответ тщательно, и есть недостающие части, которые будут написаны, рассмотрите это первый проект.

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

Где можно найти заявленные решения P vs. NP

  • Есть страница P-vs.-NP, на которой есть список таких претензий.
  • Статьи, требующие решения вопроса, регулярно публикуются на arXiv .

Другие списки, как не решить P против NP

Лэнс Фортноу, так ты думаешь, что решил P verus NP , 2009

Скотт Ааронсон, « Восемь знаков». Утверждение P ≠ NP неверно , 2010

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


Как не подойти к P против NP

Позвольте мне обсудить «как не подходить к P против NP» не в смысле идей, которые не будут работать, а в более общем смысле. P vs. NP - это легко сформулированная проблема (см. Также мой ответ здесь ):

NP = P: для каждой решаемой задачи с алгоритмом проверки полиномиального времени есть алгоритм полиномиального времени.

или эквивалентно

Для SAT есть алгоритм полиномиального времени.
SAT можно заменить любой другой NP-полной проблемой .

,

Часто люди упрощают и чрезмерно философствуют проблему и преувеличивают практическую значимость проблемы (как указано выше). Такие заявления часто предназначены для того, чтобы дать интуицию, но они никоим образом не заменяют фактическую математическую формулировку проблемы.

Теоретическая эффективность - это не то же самое, что осуществимость на практике.

Позвольте мне сначала с преувеличенными практическими последствиями.

I. Возможно, что P = NP, но это не помогает для любой проблемы на практике!

Скажем, например, что SAT находится в P, но самый быстрый алгоритм для его времени выполнения - . Этот алгоритм не имеет практического применения.2264n65536+22128

II. Вполне возможно , что P NP и мы можем решать NP-полные задачи эффективно .

Скажем, например, что SAT не находится в P, но имеет алгоритм с временем выполнения .nlglgn

Чтобы получить входное значение, которое могло бы составить вы должны использовать больше электронов, чем считается во вселенной. Таким образом, показатель степени по сути .2lgn>62

Суть в том, что P - абстрактная простая модель эффективных вычислений, сложность в худшем случае - абстрактная простая модель оценки стоимости вычислений и т. Д. Все это абстракции, но на практике никто не будет рассматривать алгоритм как в (I) выше, как эффективный алгоритм на самом деле. P - хорошая абстрактная модель, у нее хорошие свойства, она облегчает технические проблемы и полезна. Однако, как и любая математическая абстракция, она скрывает детали, которые на практике нас могут волновать. Существуют различные, более изощренные модели, но чем сложнее становится модель, тем менее приятным будет спорить.

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

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

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

Имейте в виду, что правильность и время выполнения программ не могут быть получены только при запуске программы на экземплярах . Неважно, сколько экземпляров вы попробуете, ни одной суммы не хватит. Существует бесконечно много возможных входных данных, и вы должны показать правильность и эффективность (т. Е. Время выполнения является полиномиальной) программы для всех из них. Короче, вам нужно математическое доказательство правильности и эффективности. Если вы не знаете, что такое математическое доказательство, то вам следует сначала выучить некоторую базовую математику (прочитайте учебник по дискретной математике / комбинаторике / теории графов, это хорошая тема для изучения того, что считается математическим доказательством).

Также будьте осторожны с другими утверждениями о P против NP и последствиях его ответов. Такие претензии часто основаны на аналогичных упрощениях.

Теоретики сложности на самом деле не заботятся о ответе на P против NP!

Я немного преувеличил. Конечно, мы заботимся об ответе на P против NP. Но мы заботимся об этом в контексте. P vs. NP - наша главная проблема, но она не является конечной целью. Это легко сформулированная проблема, она включает в себя много фундаментальных идей, она полезна для объяснения вопросов, которые нас интересуют, для людей, которые не знакомы с этой темой. Но мы не ищем однозначного ответа Да / Нет на этот вопрос.

Мы стремимся лучше понять природу эффективных вычислений . Мы считаем, что решение вопроса придет с таким пониманием, и это реальная причина, по которой мы заботимся об этом. Это часть огромного объема исследований. Если вы хотите почувствовать вкус того, что у нас есть, посмотрите на хороший учебник по теории сложности, например, « Теория сложности: современный подход » Ароры и Барака ( черновая версия ).

Предположим, что кто-то приходит с зашифрованным полностью формальным доказательством P NP, и мы можем проверить его правильность с очень высокой степенью достоверности, выбрав и расшифровав несколько битов доказательства (см. Доказательство с нулевым знанием и теорема PCP ). , Таким образом, мы можем проверить утверждение с вероятностью ошибки меньше, чем метеор, поразивший наш дом, мы совершенно уверены, что доказательство верное и P = NP, но мы не знаем доказательства. Это не принесет нам много удовольствия или удовольствия. Само формальное доказательство также не будет таким удовлетворительным. То, что мы ищем, не является формальным доказательством, мы ищем понимание.

Короче говоря, с точки зрения теоретика сложности

P против NP - не головоломка с ответом Да / Нет. Мы ищем ответ P против NP, потому что мы думаем, что это поможет лучше понять природу эффективных вычислений. Ответ без серьезного продвижения в нашем понимании не очень интересен.

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

Общие проблемы P = NP

Утверждения P = NP кажутся более распространенными. Я думаю, что следующее является наиболее распространенным типом. У кого-то есть идея, она пишет программу и несколько раз тестирует ее, думает, что это полиномиальное время, и правильно решает проблему NP-завершения. Как я объяснил выше, никакое количество испытаний не покажет P = NP. P = NP нуждается в математическом доказательстве , а не просто в программе, которая, кажется, решает NP-полную задачу за полиномиальное время.

Эти попытки обычно страдают от одной из двух проблем:

I. Алгоритм не совсем полиномиального времени.

II. алгоритм не решает все случаи правильно.

[будет написано]

Как проверить , что ваш алгоритм действительно не реально работать

Вы не можете показать, что ваш алгоритм работает правильно, тестируя. Но вы можете показать, что он работает неправильно, протестировав! Итак, вот как вы можете убедиться, что ваш алгоритм неверен, если вы готовы выполнить какую-то работу.

Сначала напишите программу для преобразования экземпляров SAT (в стандартном формате CNF) в NP-сложную проблему, которую вы решаете. SAT является одной из наиболее изученных NP-трудных проблем, и переход от других проблем к SAT обычно прост. Во-вторых, возьмите примеры, с которыми борются современные SAT-решатели (например, возьмите примеры из соревнования SAT), и подайте их в свой алгоритм и посмотрите, как работает ваш алгоритм. Попробуйте известные сложные примеры, такие как пропозициональный принцип Pigeonhole (и не обманывайте, жестко кодируя их как особые случаи), криптографические примеры (такие как вызовы факторинга RSA ), случайные экземпляры k-SAT вблизи порога и т. Д.

10N2

Как проверить вашу алгоритмическую идею P = NP не может работать

Если вы сделаете это, вы будете совершенно уверены, что ваш алгоритм не работает (если он работает лучше, чем современные SAT-решатели, тогда соревнуйтесь в следующем конкурсе, и многие люди будут заинтересованы в изучении вашего алгоритма и идей).

Теперь вы знаете, что это на самом деле не работает, но этого недостаточно. Ты хочешь знать почему,

причина, по которой мой алгоритм не работает, небольшая проблема, которую можно исправить, или есть фундаментальная причина, по которой он не может работать?

Иногда проблема с алгоритмом проста, и можно определить, что было концептуально неправильно. Лучший результат в том, что вы понимаете причину, по которой ваша идея не может работать. Часто это не так, ваша идея не работает, но вы не можете понять, почему. В этом случае имейте в виду:

понять, почему какая-то идея не может работать, может быть сложнее, чем решить P против NP!

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

Иногда даже нет четкой концептуальной идеи, почему алгоритм должен работать, то есть он основан на некоторой непонятной эвристике . Если у вас нет четкого концептуального представления о том, почему ваш алгоритм должен работать, то у вас не будет большого шанса понять, почему он не работает!

Вопрос 1: автор не знает определения P и NP или, что еще хуже, не понимает, что является математическим доказательством. Поскольку автору не хватает базовой математической подготовки, он не понимает, когда ему говорят, что он представляет, не является доказательством (например, шаги не следуют из предыдущих).

Проблема 2: автор путает «мы не знаем как» с «математической невозможностью». Например, они делают различные необоснованные предположения, и когда их спрашивают "почему это утверждение верно?" они отвечают «как это может быть ложным?». Одним из распространенных является предположение, что любая программа, решающая проблему, должна выполнять определенные шаги, например, она должна вычислять определенные промежуточные значения, потому что он не может придумать альтернативный способ решения проблемы.

[должен быть завершен]

[будет написано]

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

Кава
источник
Как бы мне ни нравилась страница P-vs.-NP, меня раздражает, что она не отслеживает, какие доказательства были отозваны их авторами. Для некоторых ссылок arXiv вы найдете явные уведомления о том, что «эта статья была снята» с arXiv. Я почти уверен, что есть больше отозванных доказательств, чем просто документы arXiv с явным уведомлением. Хорошо, я знаю, что отозванные доказательства не следует преувеличивать, потому что отмена «более ранней попытки доказательства» не означает, что те же авторы не будут пытаться повторить позже. Но молчание по поводу отозванных попыток доказательства по-прежнему производит необъективное впечатление.
Томас Климпел
@ Некоторые немногие «чудаковатые» авторы когда-либо «отзывали» свои статьи. невысказанный момент в списке воэгорги заключается в том, что его отчетливо менее качественное, чем в архивах архива . но, согласился, хотел бы, чтобы woegorgi мог добавить некоторую дополнительную информацию и чтобы его редактирование могло быть немного более гибким. например, он не включил мою схему P против NP в список даже после того, как отправил ему электронное письмо, хотя недавно он опубликовал еще один элемент в доказательстве фукуямы, связанный с длинным чатом cstheory.se.
vzn
1
Я ценю, что вы это снова посещаете! Похоже, я досрочно осознал награду не тому человеку. ;) Обратите внимание, что вы можете использовать stackedit.io для подготовки постов с течением времени. С нетерпением жду остальной части поста!
Рафаэль
34

Возможно, наиболее распространенным методом, который не может быть использован, является релятивизация , то есть наличие ТМ с доступом к оракулу.

AВпAзнак равноNPAпВNPВ

пNPОпОNPОA

пзнак равно?NP

Ран Г.
источник
1
Просто чтобы полностью исправить, здесь диагонализация означает прямую простую диагонализацию. Смотрите этот вопрос
Каве
1
То есть релятивизация - это не метод доказательства, а эффект, который нарушает доказательство? Можете ли вы дать / ссылку на пример доказательства, которое может быть релятивизировано?
Рафаэль
2
да, релятивизация - это не метод доказательства, это свойство доказательства (между прочим, оно не является формальным). если доказательство работает без изменений, когда все машины Тьюринга заменяются оракулами, то доказательство релятивизируется. Вы можете убедить себя, что доказательство теоремы иерархии времени в этом смысле релятивизируется, например.
Сашо Николов
10

Я предлагаю читать этот пост в блоге на Ланс Фортноу :

  1. Таким образом, вы думаете, что поселились P verus NP Вы не правы. Разберись. Иногда вы все еще можете извлечь что-то интересное из вашего некорректного доказательства.
  2. Вы считаете, что доказательства верны. Ваше мнение неверно. Вернитесь к шагу 1.
  3. Вы делаете какие-либо предположения или сокращения, даже кажущиеся маленькими и очевидными? Используете ли вы такие слова, как «ясно», «очевидно», «легко увидеть», «должен», «должен» или «вероятно»? Вы утверждаете, что решили, возможно, самый важный вопрос во всей математике. Вы не можете делать предположения. Вернитесь к шагу 1.
  4. NК
  5. Вы отправляете свою статью в онлайн-архив. Может быть, некоторые люди скажут вам, что отсутствует или неправильно в вашей газете. Это должно заставить вас перейти к шагу 1. Но вместо этого вы вносите несколько бессмысленных изменений в свою бумагу и перепечатываете.
  6. В конце концов люди игнорируют вашу газету. Вы удивляетесь, почему вы не получаете славу и богатство.
  7. Вы отправляете свою статью в журнал.
  8. Бумага отклонена. Если вы умны, вы вернетесь к шагу 1. Но если бы вы были умны, вы бы никогда не добрались до шага 7.
  9. Вы жалуетесь редактору, что либо редактор не понимает доказательства, либо его легко исправить. Вы в шоке респектабельный редактор или журнал будет относиться к вашей статье таким образом.
  10. Вы повторно подаете бумагу, апеллируете, пробуете другие журналы, но все безрезультатно.
  11. Вы убеждены, что «истеблишмент» намеренно подавляет вашу статью, потому что наше поле станет гораздо менее интересным, если мы решим проблему P против NP, поэтому мы должны держать ее открытой любой ценой.
  12. Если я скажу тебе иначе, поверишь ли ты мне?
Кава
источник
7
Вопрос требует «подходов, которые, как было доказано, не работают» и подходов, «имеющих историю неудач», и в этом ответе не упоминается какой-либо подход.
Tsuyoshi Ito
6
Я хочу сказать, что поскольку сообщение в блоге вообще не отвечает на вопрос, копировать и вставлять его бессмысленно.
Цуёси Ито
7
Это действительно не отвечает на вопрос. Сообщение в блоге - выдуманный список шагов типичного P = NP? кривошипно проходит. Хотя это интересно, это не дает мне конкретных теорий , которые, как было показано, не способны разделить (или свернуть) P и NP.
Рафаэль
4
Как насчет этого? Этот вопрос требует барьеров для доказательства P! = NP. Препятствиями в этом ответе (как указано в комментариях) являются «предполагать что-то», «плохая интерпретация», «говорить что-то ясно», «верить во что-то». Эти барьеры являются слишком общими в том смысле, что они являются барьерами для доказательства чего-либо, а не являются конкретными барьерами для доказательства P! = NP.
Тайсон Уильямс
1
в комментариях, хотя они действительны, отсутствует базовый пункт. блог был написан Лэнсом Фортнау, экспертом по теории сложности и мировым авторитетом в этой области; он только что выпустил новую книгу о P против NP Golden Ticket . поэтому он говорит в основном из личного опыта.
vzn
2

Вот несколько неясный / глубокий / трудный / внутренний угол / эталон / поворот, касающийся подходов через схемы, относящиеся к 1980-м годам, на которые мне указал много лет назад Лука Тревизан в другом месте в киберпространстве, а также еще раз подтвердил Стасис Юкна, автор превосходного ссылка рядом с предметом, Сложность булевой функции: достижения и рубежи (Алгоритмы и комбинаторика, том 27 ).

Можно заметить более раннюю тенденцию в мышлении Разборова, которая в итоге привела к статье « Естественные доказательства» (так называемая «натурализация»). Ссылка [273] очень техническая и трудная, и, кажется, ее не цитируют, не строят, не расширяют или не повторяют в более поздних статьях / книгах, хотя «Естественные доказательства» можно рассматривать как более позднее обобщение. выдержка из Джона Э Сэвиджса превосходная ссылка Модели вычислений p457

Ω(N2)N

[270] А.А. Разборов, Нижние оценки монотонной сложности некоторых булевых функций, Докл. Акад. Наук СССР (Советский матем. Докл.) 281 (1985), 798–801 (на русском языке); Английский перевод в советской математике. Докл. 31 (1985), 354–357

[271] А.А. Разборов, “Нижняя граница сложности монотонной сети логического перманента”, Матем. Заметки 37 (1985), 887–900, (на русском языке); Английский перевод в математике. Примечания 37 (6) (1985), 485–493.

[273] А.А. Разборов, “О методе приближений”, Тр. 21-ая Анн. ACM Symp. Теория вычислений (1989), 167–176.

ВЗН
источник
2
Я не понимаю, как это отвечает на вопрос «как не доказать P? = NP». Прямо сейчас это похоже на какие-то предположения о чьих-то мыслях.
Юхо
2
Конечно, я только предлагаю сделать все это явным. Сложность схемы даже не материал уровня старшекурсника, поэтому некоторые предпосылки оправданы. Справедливо ожидать, что читатель не будет экспертом в теории сложности.
Юхо
@ юхо хорошо. Однажды увидев книгу Savage [которая очень «ориентирована на контуры»), использованную в классе бакалавриата, меня это тоже удивило. согласился с его предварительным материалом, следовательно, формулировка 1-го предложения. Что касается «спекуляций на мыслях», то их нет, если не упомянуть собственные мысли Разборова, написанные / записанные в его собственных работах.
vzn
1
и, между прочим, в целом это очень сложный вопрос (не на самом деле уровень бакалавриата), и другие ответы продвинуты и, как правило, за пределами уровня бакалавриата.
vzn