Проблема P против NP - P versus NP problem

Нерешенная проблема в информатике :

Если решение проблемы легко проверить на правильность, должна ли проблема быть легко решаемой?

Проблема P и NP - основная нерешенная проблема в информатике . Он спрашивает, можно ли быстро решить каждую проблему, решение которой можно быстро проверить.

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

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

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

Это одна из семи задач, отобранных Математическим институтом Клэя, из семи задач, удостоенных премии тысячелетия , каждая из которых имеет приз в размере 1 000 000 долларов США за первое правильное решение.

Пример

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

История

Точная формулировка проблемы P и NP была введена в 1971 году Стивеном Куком в его основополагающей статье «Сложность процедур доказательства теорем» (и независимо Леонидом Левиным в 1973 году).

Хотя проблема P и NP была формально определена в 1971 году, существовали и предыдущие намёки на связанные с этим проблемы, сложность доказательства и возможные последствия. В 1955 году математик Джон Нэш написал письмо в АНБ , в котором предположил, что для взлома достаточно сложного кода потребуется время, экспоненциально зависящее от длины ключа. Если бы это было доказано (а Нэш был достаточно скептически настроен), это означало бы то, что сейчас называется P ≠ NP, поскольку предложенный ключ можно легко проверить за полиномиальное время. Еще одно упоминание о возникшей проблеме произошла в 1956 письме , написанном Курта Гёделя на Джона фон Неймана . Гёдель спросил, можно ли решить доказательство теорем (которое теперь известно как NP-полное ), за квадратичное или линейное время , и указал на одно из наиболее важных следствий: если так, то открытие математических доказательств можно автоматизировать.

Контекст

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

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

В этой теории класс P состоит из всех тех задач принятия решений (определенных ниже ), которые могут быть решены на детерминированной последовательной машине за время, полиномиальное по размеру входных данных; класс NP состоит из всех тех задач принятия решений, положительные решения которых могут быть проверены за полиномиальное время при наличии правильной информации или, что эквивалентно, чье решение может быть найдено за полиномиальное время на недетерминированной машине. Ясно, что P ⊆ NP. Возможно, самый большой открытый вопрос в теоретической информатике касается взаимоотношений между этими двумя классами:

P равно NP?

С 2002 года Уильям Гасарх провел три опроса исследователей по этому и смежным вопросам. Уверенность в том, что P ≠ NP растет - в 2019 году 88% верили в P ≠ NP, по сравнению с 83% в 2012 году и 61% в 2002 году. Если ограничиться только экспертами, ответы 2019 года составили 99%, которые верят P ≠ NP. Эти опросы ничего не говорят о том, верно ли P = NP, как заявил сам Гасарх: «Это не приближает нас ни к решению P =? NP, ни к знанию того, когда оно будет решено, но оно пытается быть объективным. отчет о субъективном мнении этой эпохи. ″

NP-полнота

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

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

NP-сложные задачи - это те, по крайней мере, такие же сложные, как и NP-задачи; т.е. все задачи NP сводятся (за полиномиальное время) к ним. NP-сложные проблемы не обязательно должны быть в NP; т.е. им не обязательно иметь решения, проверяемые за полиномиальное время.

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

На основании одного определения не очевидно, что существуют NP-полные проблемы; однако тривиальная и надуманная NP-полная проблема может быть сформулирована следующим образом: при описании машины Тьюринга M, гарантированно останавливающейся за полиномиальное время, существует ли вход полиномиального размера, который M примет? Это в NP, потому что (учитывая ввод) просто проверить, принимает ли M ввод, моделируя M ; он является NP-полным, потому что верификатор для любого конкретного случая проблемы в NP может быть закодирован как машина M с полиномиальным временем, которая принимает решение, которое нужно проверить, в качестве входных данных. Тогда вопрос о том, является ли экземпляр экземпляром «да» или «нет», определяется тем, существует ли допустимый ввод.

Первой естественной проблемой, которая оказалась NP-полной, была проблема булевой выполнимости, также известная как SAT. Как отмечалось выше, это теорема Кука – Левина; его доказательство того, что выполнимость является NP-полной, содержит технические подробности о машинах Тьюринга, поскольку они связаны с определением NP. Однако после того, как эта проблема была доказана как NP-полная, доказательство редукцией предоставило более простой способ показать, что многие другие задачи также являются NP-полными, включая игру Судоку, обсуждавшуюся ранее. В этом случае доказательство показывает, что решение судоку за полиномиальное время можно также использовать для завершения латинских квадратов за полиномиальное время. Это, в свою очередь, дает решение проблемы разбиения трехчастных графов на треугольники, которые затем можно использовать для поиска решений для особого случая SAT, известного как 3-SAT, который затем обеспечивает решение для общей логической выполнимости. Таким образом, решение судоку за полиномиальное время с помощью ряда механических преобразований приводит к полиномиальному решению выполнимости, которое, в свою очередь, может быть использовано для решения любой другой NP-задачи за полиномиальное время. Используя подобные преобразования, можно свести друг к другу обширный класс, казалось бы, не связанных между собой проблем, и в некотором смысле они являются «одной и той же проблемой».

Более серьезные проблемы

Хотя неизвестно, является ли P = NP, проблемы за пределами P известны. Так же, как класс P определяется в терминах полиномиального времени выполнения, класс EXPTIME представляет собой набор всех задач решения, которые имеют экспоненциальное время выполнения. Другими словами, любая проблема в EXPTIME решается детерминированной машиной Тьюринга за время O (2 p ( n ) ), где p ( n ) - полиномиальная функция от n . Задача решения является EXPTIME-завершенной, если она находится в EXPTIME, и каждая проблема в EXPTIME имеет полиномиальное сокращение «многие-один» . Известно, что ряд проблем завершается EXPTIME. Поскольку можно показать, что P ≠ EXPTIME, эти проблемы выходят за рамки P, и поэтому требуют более чем полиномиального времени. Фактически, согласно теореме о временной иерархии , они не могут быть решены за значительно меньшее, чем экспоненциальное время. Примеры включают поиск идеальной стратегии для шахматных позиций на доске N × N и аналогичные задачи для других настольных игр.

Проблема определения истинности утверждения в арифметике Пресбургера требует еще больше времени. Фишер и Рабин доказали в 1974 году, что каждый алгоритм, определяющий истинность утверждений Пресбургера длины n, имеет время выполнения, по крайней мере, для некоторой константы c . Следовательно, известно, что проблема требует большего, чем экспоненциальное время выполнения. Еще более трудными являются неразрешимые проблемы , такие как проблема остановки . Они не могут быть полностью решены никаким алгоритмом в том смысле, что для любого конкретного алгоритма существует по крайней мере один вход, для которого этот алгоритм не даст правильного ответа; он либо даст неправильный ответ, либо закончит, не дав окончательный ответ, либо будет работать вечно, вообще не получив никакого ответа.

Также возможно рассмотреть другие вопросы, помимо проблем с решением. Один из таких классов, состоящий из задач подсчета, называется #P : в то время как проблема NP спрашивает «Есть ли решения?», Соответствующая задача #P спрашивает: «Сколько существует решений?» Ясно, что проблема #P должна быть не менее сложной, чем соответствующая проблема NP, поскольку счетчик решений сразу сообщает, существует ли хотя бы одно решение, если счетчик больше нуля. Удивительно, но некоторые задачи #P, которые считаются сложными, соответствуют простым (например, линейному времени) P-задачам. Для этих проблем очень легко определить, существуют ли решения, но трудно сказать, сколько. Многие из этих задач являются # P-полными и, следовательно, являются одними из самых сложных проблем в #P, поскольку решение любой из них за полиномиальное время позволило бы решить все другие проблемы #P за полиномиальное время.

Неизвестно, что проблемы в NP находятся в P или NP-полных

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

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

Задача целочисленной факторизации - это вычислительная проблема определения факторизации на простые множители данного целого числа. Сформулированная как проблема решения, это проблема определения того, имеет ли вход множитель меньше k . Эффективный алгоритм целочисленной факторизации неизвестен, и этот факт лежит в основе нескольких современных криптографических систем, таких как алгоритм RSA . Проблема целочисленной факторизации есть в NP и co-NP (и даже в UP и co-UP). Если проблема является NP-полной, иерархия полиномиального времени схлопнется до своего первого уровня (т. Е. NP = co-NP). Самый известный алгоритм для целочисленной факторизации - это решето общего числового поля , которое занимает ожидаемое время.

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

P означает "легкий"?

График показывает зависимость времени выполнения от размера задачи для задачи о ранце с использованием современного специализированного алгоритма. Квадратичная форма предполагает , что алгоритмическая сложность задачи представляет собой О ((журнале ( п )) 2 ).

Все вышеизложенное предполагало, что P означает «легко», а «не в P» означает «сложно», - предположение, известное как тезис Кобхэма . Это распространенное и достаточно точное предположение в теории сложности; однако у него есть некоторые предостережения.

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

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

Наконец, есть типы вычислений, которые не соответствуют модели машины Тьюринга, на которой определены P и NP, например квантовые вычисления и рандомизированные алгоритмы .

Причины полагать, что P ≠ NP или P = NP

Кук обеспечивает пересчет задачи в Р VERSUS NP ПРОБЛЕМА как: Does P = NP ? . Согласно опросам, большинство компьютерных ученых считают, что P ≠ NP. Основная причина этого убеждения состоит в том, что после десятилетий изучения этих проблем никто не смог найти алгоритм с полиномиальным временем для любой из более чем 3000 важных известных NP-полных проблем (см. Список NP-полных проблем ). Эти алгоритмы искали задолго до того, как была даже определена концепция NP-полноты ( 21 NP-полная проблема Карпа , среди первых найденных, были хорошо известными существующими проблемами в то время, когда их NP-полнота была показана). Более того, результат P = NP будет подразумевать множество других поразительных результатов, которые в настоящее время считаются ложными, например NP = co-NP и P = PH .

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

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

С другой стороны, некоторые исследователи полагают, что верить P ≠ NP слишком самоуверенно и что исследователи также должны изучить доказательства того, что P = NP. Например, в 2002 году были сделаны такие заявления:

Главный аргумент в пользу P ≠ NP - полное отсутствие принципиального прогресса в области исчерпывающего поиска. Это, на мой взгляд, очень слабый аргумент. Пространство алгоритмов очень велико, и мы находимся только в начале его освоения. [...] Резолюция Великой теоремы Ферма также показывает, что очень простые вопросы могут быть решены только очень глубокими теориями.

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

Последствия решения

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

P = NP

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

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

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

  • Существующие реализации криптографии с открытым ключом , основа для многих современных приложений безопасности, таких как безопасные финансовые транзакции через Интернет.
  • Симметричные шифры, такие как AES или 3DES , используются для шифрования данных связи.
  • Криптографическое хеширование , лежащее в основе криптовалют блокчейна, таких как биткойны , и используется для проверки подлинности обновлений программного обеспечения. Для этих приложений проблема поиска прообраза, который хеширует заданное значение, должна быть сложной, чтобы быть полезной, и в идеале должна требовать экспоненциального времени. Однако, если P = NP, то поиск прообраза M может быть выполнен за полиномиальное время путем сокращения до SAT.

Их необходимо будет изменить или заменить теоретически безопасными решениями, которые по своей сути не основаны на неэквивалентности P-NP.

С другой стороны, есть колоссальные положительные последствия, которые могут возникнуть в результате решения многих в настоящее время математически трудноразрешимых проблем. Например, многие задачи исследования операций являются NP-полными, например, некоторые типы целочисленного программирования и задача коммивояжера . Эффективные решения этих проблем будут иметь огромное значение для логистики. Многие другие важные проблемы, такие как некоторые проблемы предсказания структуры белка , также являются NP-полными; если бы эти проблемы были эффективно решены, это могло бы стимулировать значительный прогресс в науках о жизни и биотехнологии.

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

Если бы действительно существовала машина с φ (n) ∼ k ⋅ n (или даже ∼ k ⋅ n 2 ), это имело бы очень важные последствия. А именно, это, очевидно, означало бы, что, несмотря на неразрешимость Entscheidungsproblem , умственная работа математика над вопросами типа «да или нет» может быть полностью заменена машиной. В конце концов, нужно было бы просто выбрать натуральное число n настолько большим, что, когда машина не выдаст результат, не было смысла больше думать о проблеме.

Точно так же Стивен Кук (предполагая не только доказательство, но и практически эффективный алгоритм) говорит:

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

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

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

[...] если вы представите число M, которое конечно, но невероятно велико - например, число 10 ↑↑↑↑ 3, обсуждаемое в моей статье о «преодолении конечности», - тогда существует огромное количество возможных алгоритмов, которые делают n M побитовые операции или операции сложения или сдвига на n заданных битах, и действительно трудно поверить, что все эти алгоритмы не работают. Однако я хочу сказать, что я не верю, что равенство P = NP окажется полезным, даже если оно будет доказано, потому что такое доказательство почти наверняка будет неконструктивным.

Схема классов сложности при условии, что P   NP. Существование проблем внутри NP, но вне P и NP-полных при этом предположении было установлено теоремой Ладнера .

P ≠ NP

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

Кроме того, P ≠ NP по-прежнему оставляет открытой среднюю сложность сложных задач в NP. Например, возможно, что SAT требует экспоненциального времени в худшем случае, но что почти все случайно выбранные его экземпляры эффективно разрешимы. Рассел Импальяццо описал пять гипотетических «миров», которые могут возникнуть в результате различных возможных решений вопроса о средней сложности. Они варьируются от «Algorithmica», где P = NP и проблемы, подобные SAT, могут быть эффективно решены во всех случаях, до «Cryptomania», где P ≠ NP и создание сложных экземпляров проблем вне P легко, с тремя промежуточными возможностями, отражающими различные возможные распределения сложности по экземплярам NP-трудных задач. «Мир», где P ≠ NP, но все проблемы в NP решаемы в среднем случае, в статье называется «эвристикой». На семинаре Принстонского университета в 2009 году был изучен статус пяти миров.

Результаты о сложности доказательства

Хотя сама проблема P = NP остается открытой, несмотря на приз в миллион долларов и огромное количество целенаправленных исследований, попытки решить эту проблему привели к появлению нескольких новых методов. В частности, некоторые из наиболее плодотворных исследований, связанных с проблемой P = NP, показали, что существующие методы доказательства недостаточно эффективны, чтобы ответить на этот вопрос, таким образом предполагая, что требуются новые технические подходы.

В качестве дополнительного доказательства сложности проблемы практически все известные методы доказательства в теории вычислительной сложности попадают в одну из следующих классификаций, каждая из которых, как известно, недостаточна для доказательства того, что P ≠ NP:

Классификация Определение
Релятивизирующие доказательства Представьте себе мир, в котором каждому алгоритму разрешено делать запросы к некоторой фиксированной подпрограмме, называемой оракулом (черный ящик, который может отвечать на фиксированный набор вопросов за постоянное время, например черный ящик, который решает любую заданную задачу коммивояжера за 1 шаг) , и время работы оракула не засчитывается во время работы алгоритма. Большинство доказательств (особенно классических) одинаково применимы в мире с оракулами, независимо от того, что делает оракул. Эти доказательства называются релятивизирующими . В 1975 году Бейкер, Гилл и Соловей показали, что P = NP для некоторых оракулов, а P ≠ NP для других оракулов. Поскольку релятивизирующие доказательства могут доказать только утверждения, которые единообразно истинны по отношению ко всем возможным оракулам, это показало, что релятивизирующие методы не могут разрешить P = NP.
Естественные доказательства В 1993 году Александр Разборов и Стивен Рудич определили общий класс методов доказательства для нижних оценок сложности схем, которые называются естественными доказательствами . В то время все ранее известные нижние границы схемы были естественными, и сложность схемы считалась очень многообещающим подходом для решения P = NP. Однако Разборов и Рудич показали, что если существуют односторонние функции , то никакой естественный метод доказательства не может отличить P от NP. Хотя формально существование односторонних функций никогда не было доказано, большинство математиков полагают, что они существуют, и доказательство их существования было бы гораздо более сильным утверждением, чем P ≠ NP. Таким образом, маловероятно, что одни только естественные доказательства могут разрешить P = NP.
Алгебризация доказательств После результата Бейкера-Гилла-Соловея новые нерелятивизирующие методы доказательства были успешно использованы для доказательства того, что IP = PSPACE . Однако в 2008 году Скотт Ааронсон и Ави Вигдерсон показали, что основной технический инструмент, используемый в доказательстве IP = PSPACE, известный как арифметизация , также недостаточен для решения P = NP.

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

Эти препятствия также побудили некоторых компьютерных ученых предположить, что проблема P и NP может быть независимой от стандартных систем аксиом, таких как ZFC (в них нельзя доказать или опровергнуть). Интерпретация результата независимости может заключаться в том, что либо для любой NP-полной задачи не существует алгоритма с полиномиальным временем, и такое доказательство не может быть построено в (например) ZFC, либо могут существовать алгоритмы с полиномиальным временем для NP-полных задач, но в ZFC невозможно доказать, что такие алгоритмы верны. Однако, если можно показать, используя известные в настоящее время методы, что проблема не может быть решена даже при гораздо более слабых предположениях, расширяющих аксиомы Пеано (PA) для целочисленной арифметики, тогда обязательно будет существовать почти - полиномиальные алгоритмы для каждой задачи в NP. Следовательно, если кто-то считает (как и большинство теоретиков сложности), что не все проблемы в NP имеют эффективные алгоритмы, из этого следует, что доказательства независимости с использованием этих методов невозможны. Кроме того, этот результат подразумевает, что доказать независимость от PA или ZFC с помощью известных в настоящее время методов не проще, чем доказать существование эффективных алгоритмов для всех проблем в NP.

Заявленные решения

Хотя проблема P и NP обычно считается нерешенной, многие любители и некоторые профессиональные исследователи заявляют о своих решениях. Герхард Дж. Вёгингер ведет список, который по состоянию на 2016 год содержит 62 предполагаемых доказательства P = NP, 50 доказательств P ≠ NP, 2 доказательства недоказуемости проблемы и одно доказательство неразрешимости. Ясно, что по крайней мере 53 из этих доказательств неверны. Некоторые попытки решить проблему P и NP привлекли к себе внимание средств массовой информации, хотя с тех пор эти попытки были опровергнуты.

Логические характеристики

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

Рассмотрим все языки конечных структур с фиксированной сигнатурой, включая отношение линейного порядка . Тогда все такие языки в P могут быть выражены в логике первого порядка с добавлением подходящего комбинатора с наименьшей фиксированной точкой . Фактически, это в сочетании с порядком позволяет определять рекурсивные функции. Пока сигнатура содержит хотя бы один предикат или функцию в дополнение к выделенному отношению порядка, так что объем пространства, занимаемого для хранения таких конечных структур, фактически является полиномиальным по отношению к количеству элементов в структуре, это точно характеризует P.

Точно так же NP - это набор языков, выражаемых в экзистенциальной логике второго порядка, то есть логика второго порядка, ограниченная исключением универсальной квантификации по отношениям, функциям и подмножествам. Языки в полиномиальной иерархии , PH , соответствуют всем логике второго порядка. Таким образом, вопрос «является ли P правильным подмножеством NP» можно переформулировать следующим образом: «способна ли экзистенциальная логика второго порядка описывать языки (конечных линейно упорядоченных структур с нетривиальной сигнатурой), которые логика первого порядка с наименьшей фиксированной точкой не может?» . Слово «экзистенциальный» можно даже исключить из предыдущей характеристики, поскольку P = NP тогда и только тогда, когда P = PH (поскольку первое установило бы, что NP = co-NP, что, в свою очередь, подразумевает, что NP = PH).

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

Известно, что ни один алгоритм для любой NP-полной задачи не работает за полиномиальное время. Однако существуют алгоритмы, известные для NP-полных задач, которые обладают тем свойством, что если P = NP, то алгоритм выполняется за полиномиальное время при приеме экземпляров (хотя и с огромными константами, что делает алгоритм непрактичным). Однако эти алгоритмы не квалифицируются как полиномиальное время, потому что их время работы при отклонении экземпляров не полиномиально. Следующий алгоритм, принадлежащий Левину (без какой-либо ссылки), является таким примером ниже. Он правильно принимает NP-полный язык SUBSET-SUM . Он запускается за полиномиальное время на входах, которые находятся в SUBSET-SUM тогда и только тогда, когда P = NP:

// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
  FOR M = 1...K
    Run program number M for K steps with input S
    IF the program outputs a list of distinct integers
      AND the integers are all in S
      AND the integers sum to 0
    THEN
      OUTPUT "yes" and HALT

Если и только если P = NP, то это алгоритм с полиномиальным временем, принимающий NP-полный язык. «Принятие» означает, что он дает ответы «да» за полиномиальное время, но может работать бесконечно, если ответ «нет» (также известный как полуалгоритм ).

Этот алгоритм чрезвычайно непрактичен, даже если P = NP. Если самая короткая программа, которая может решить SUBSET-SUM за полиномиальное время, имеет длину b бит, вышеупомянутый алгоритм сначала попробует по крайней мере 2 b - 1 другую программу.

Формальные определения

P и NP

Концептуально говоря, проблема решения - это проблема, которая принимает на входе некоторую строку w в алфавите Σ и выводит «да» или «нет». Если существует алгоритм (скажем, машина Тьюринга или компьютерная программа с неограниченной памятью), который может дать правильный ответ для любой входной строки длины n не более чем за cn k шагов, где k и c - константы, не зависящие от входной строки , то мы говорим, что проблема может быть решена за полиномиальное время, и помещаем ее в класс P. Формально P определяется как набор всех языков, которые могут быть решены с помощью детерминированной машины Тьюринга с полиномиальным временем. То есть,

куда

а детерминированная машина Тьюринга с полиномиальным временем - это детерминированная машина Тьюринга M, которая удовлетворяет следующим двум условиям:

  1. M останавливается на всех входах w и
  2. существует такое, что , где O относится к нотации большого O и

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

Пусть L - язык над конечным алфавитом Σ.

L ∈ NP тогда и только тогда, когда существует бинарное отношение и натуральное число k такие, что выполняются следующие два условия:

  1. Для всех , такой , что ( х , у ) ∈ R и ; а также
  2. язык над разрешим на детерминированной машине Тьюринга за полиномиальное время.

Тьюринг машин , которая решает , L R называется верификатором для L и у такие , что ( х , у ) ∈ R называется сертификатом членства в х в л .

В общем, верификатор не обязательно должен быть полиномиальным. Однако для того, чтобы L был в NP, должен быть верификатор, работающий за полиномиальное время.

Пример

Позволять

Очевидно, что вопрос о том, дано ли х представляет собой композит эквивалентен вопрос о том , х является членом композита. Можно показать, что COMPOSITE ∈ NP, проверив, что он удовлетворяет приведенному выше определению (если мы отождествляем натуральные числа с их двоичными представлениями).

КОМПОЗИТ также оказывается в P, факт, продемонстрированный изобретением теста простоты AKS .

NP-полнота

Есть много эквивалентных способов описания NP-полноты.

Пусть L - язык над конечным алфавитом Σ.

L является NP-полным тогда и только тогда, когда выполняются следующие два условия:

  1. L ∈ NP; а также
  2. любой L в NP полиномиально сводится к L (записывается как ), где тогда и только тогда, когда выполняются следующие два условия:
    1. Там существует F  : Σ * → Σ *, что для всех ш в Е * мы имеем: ; а также
    2. существует машина Тьюринга с полиномиальным временем, которая останавливается с f ( w ) на своей ленте на любом входе w .

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

Популярная культура

Фильм « Коммивояжер » режиссера Тимоти Ланзона - это история четырех математиков, нанятых правительством США для решения задачи «P против NP».

В шестом эпизоде седьмого сезона Симпсонов « Дом ужасов VI » уравнение P = NP видно вскоре после того, как Гомер случайно наткнулся на «третье измерение».

Во втором эпизоде сезона 2 Elementary , «Решите для X» вращается вокруг Шерлока и Ватсона , расследующие убийства математиков , которые пытались решить P против NP.

Смотрите также

Примечания

использованная литература

Источники

дальнейшее чтение

внешние ссылки