Проблема P и NP

Нерешенная задача в информатике :

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

(еще нерешенные проблемы по информатике)

Проблема 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-полными)

Основная статья: 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 ) — полиномиальная функция от n . Задача решения является EXPTIME-полной, если она находится в EXPTIME, и каждая проблема в EXPTIME имеет полиномиальное сведение к ней «много-единица». Известно, что ряд задач EXPTIME-полны. Поскольку можно показать, что P ≠ EXPTIME, эти проблемы находятся за пределами P и поэтому требуют времени, превышающего полиномиальное. Фактически, согласно теореме об иерархии времени , они не могут быть решены за значительно меньшее, чем экспоненциальное время. Примеры включают поиск идеальной стратегии для шахматных позиций на N × N. доске и аналогичные проблемы для других настольных игр.

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

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

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

Основная статья: NP-средний уровень

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

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

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

$O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)$

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

Означает ли P «легко»?

На графике показана зависимость времени выполнения от размера задачи для задачи о рюкзаке современного специализированного алгоритма. Квадратичная аппроксимация предполагает, что алгоритмическая сложность задачи равна O((log( n )) ² ).

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

Во-первых, на практике это может быть ложным. Теоретический полиномиальный алгоритм может иметь чрезвычайно большие постоянные коэффициенты или показатели степени, что делает его непрактичным. Например, проблема определения ли граф G того, содержит H элемент минорный , где H фиксирован, может быть решена за время выполнения O ( n ² ), где n количество вершин в G. — Однако за большим обозначением O скрывается константа, которая суперэкспоненциально зависит H. от Константа больше, чем $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ (используя направленное вверх ), и где h — количество вершин в H. обозначение Кнута ,

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

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

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

переформулирует проблему Кук в книге «Проблема P против NP» следующим образом: «Р = 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 является полное отсутствие фундаментального прогресса в области перебора. На мой взгляд, это очень слабый аргумент. Пространство алгоритмов очень велико и мы находимся только в начале его исследования. [...] Разрешение Великой теоремы Ферма также показывает, что очень простые вопросы могут быть решены только с помощью очень глубоких теорий.

—  Moshe Y. Vardi , Rice University

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

— Анил Нерод , Корнелльский университет

DLIN vs NLIN

Когда в определениях P и NP заменяется «линейное время на многоленточной машине Тьюринга» на «полиномиальное время», получаются классы DLIN и NLIN . Известно что DLIN≠NLIN.

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

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

П = НП

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

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

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

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

Они потребуют модификации или замены теоретически безопасными решениями, которые не предполагают P ≠ NP.

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

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

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

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

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

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

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

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

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

П ≠ НП

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

P ≠ NP по-прежнему оставляет открытым вопрос о сложности сложных задач в NP в среднем случае. Например, возможно, что в худшем случае SAT требует экспоненциального времени, но почти все случайно выбранные его случаи эффективно решаемы. Рассел Импальяццо описал пять гипотетических «миров», которые могут возникнуть в результате различных возможных решений вопроса сложности среднего случая. Они варьируются от «Алгоритмики», где P = NP и такие проблемы, как SAT, могут быть эффективно решены во всех случаях, до «Криптомании», где 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. Арифметизация преобразует операции алгоритма в алгебраические и основные арифметические символы, а затем использует их для анализа работы. В доказательстве IP = PSPACE они преобразуют черный ящик и логические схемы в алгебраическую задачу. Как упоминалось ранее, было доказано, что этот метод непригоден для решения P = NP и других проблем временной сложности .

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

Эти барьеры заставляют некоторых ученых-компьютерщиков предполагать, что проблема P и NP может быть независимой от стандартных систем аксиом, таких как ZFC (в их рамках невозможно доказать или опровергнуть). Результат независимости может означать, что либо P ≠ NP, и это недоказуемо (например) в ZFC, либо что P = NP, но в ZFC недоказуемо корректность любых алгоритмов с полиномиальным временем. Однако если проблема неразрешима даже при гораздо более слабых предположениях, расширяющих аксиомы Пеано для целочисленной арифметики, то для всех задач NP существуют алгоритмы с почти полиномиальным временем. Следовательно, если предположить (как это делает большинство теоретиков сложности), что некоторые задачи NP не имеют эффективных алгоритмов, доказательства независимости с помощью этих методов невозможны. Это также означает, что доказать независимость от PA или ZFC с помощью современных методов не проще, чем доказать, что все задачи 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

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

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

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

П и НП

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

$\mathbf {P} =\{L:L=L(M){\text{ for some deterministic polynomial-time Turing machine }}M\}$

где

$L(M)=\{w\in \Sigma ^{*}:M{\text{ accepts }}w\}$

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

1. M останавливается на всех входах w и
2. существует $k\in N$ такой, что $T_{M}(n)\in O(n^{k})$, где O относится к большому обозначению O , а

$T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}$

$t_{M}(w)={\text{ number of steps }}M{\text{ takes to halt on input }}w.$

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

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

L ∈ NP тогда и только тогда, когда существует бинарное отношение $R\subset \Sigma ^{*}\times \Sigma ^{*}$ и положительное целое число k такое, что выполняются следующие два условия:

1. Для всех $x\in \Sigma ^{*}$, $x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ такой, что ( x , y ) ∈ R и $|y|\in O(|x|^{k})$; и
2. язык $L_{R}=\{x\#y:(x,y)\in R\}$ над $\Sigma \cup \{\#\}$ разрешима детерминированной машиной Тьюринга за полиномиальное время.

Машина Тьюринга, которая решает L _R, называется верификатором для L и a y, , что ( x , y ) ∈ R, сертификатом принадлежности x такого к L. называется

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

Пример

Позволять

$\mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ for integers }}p,q>1\right\}$

$R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ and }}y{\text{ divides }}x\right\}.$

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

COMPOSITE также находится в P, и этот факт продемонстрирован изобретением теста простоты AKS .

NP-полнота

Основная статья: NP-полнота

Существует множество эквивалентных способов описания NP-полноты.

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

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

1. L € NP; и
2. любой L' в NP полиномиально сводится к L (записанный как $L'\leq _{p}L$), где $L'\leq _{p}L$ тогда и только тогда, когда выполняются следующие два условия:
   1. Существует f : Σ* → Σ* такой, что для всех w из Σ* имеем: $(w\in L'\Leftrightarrow f(w)\in L)$; и
   2. существует машина Тьюринга с полиномиальным временем, которая останавливается с f ( w ) на своей ленте на любом входном сигнале w .

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

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

Хотя проблема P и NP обычно считается нерешенной, многие любители и некоторые профессиональные исследователи предложили решения. Герхард Дж. Вегингер составил список из 116 предполагаемых доказательств с 1986 по 2016 год, из которых 61 было доказательством P = NP, 49 было доказательством P ≠ NP, а 6 доказали другие результаты, например, что проблема неразрешима. Некоторые попытки решить проблему P и NP ненадолго привлекли внимание средств массовой информации. хотя эти попытки были опровергнуты.

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

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

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

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

Похожие проблемы

• Проблема R и RE , где R — аналог класса P, а RE — аналог класса NP. Эти классы не равны, поскольку существуют неразрешимые, но проверяемые проблемы, например, десятая проблема Гильберта, которая является RE-полной .
• Похожая проблема существует в теории алгебраической сложности : проблема VP vs. VNP . Эта проблема до сих пор не решена.

См. также

• Сложность игры
• Список нерешенных задач по математике
• Гипотеза об уникальных играх
• Нерешенные проблемы информатики

Источники

• Рэйчел Кроуэлл (28 мая 2021 г.). «Самые нерешенные вопросы математики остаются по большей части загадкой. Только одна из семи задач Премии тысячелетия, названных 21 год назад, была решена» . www. Scientificamerican.com . Проверено 21 июня 2021 г. Эта проблема касается вопроса о том, имеют ли вопросы, которые легко проверить (класс запросов, называемый NP), решения, которые легко найти (класс, называемый P).
• Хош, Уильям Л. (11 августа 2009 г.). «Математические задачи P и NP» . Британская энциклопедия . Проверено 20 июня 2021 г.
• «Проблема P против NP» . www.claymath.org (Кук, Левин) . Проверено 20 июня 2021 г. Предположим, вы организуете жилье для группы из четырехсот студентов университета. Количество мест ограничено, и места в общежитии получат только сто студентов. Чтобы усложнить ситуацию, декан предоставил вам список пар несовместимых студентов и потребовал, чтобы ни одна пара из этого списка не фигурировала в вашем окончательном выборе. Это пример того, что ученые-компьютерщики называют NP-проблемой...

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

• Кормен, Томас (2001). Введение в алгоритмы . Кембридж: MIT Press . ISBN  978-0-262-03293-3 .
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN  9780716710455 . МР   0519066 . OCLC   247570676 .
• Гольдрейх, Одед (2010). P, NP и NP-полнота . Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-12254-2 . Онлайн черновики
• Иммерман, Нил (1987). «Языки, фиксирующие классы сложности». SIAM Journal по вычислительной технике . 16 (4): 760–778. CiteSeerX   10.1.1.75.3035 . дои : 10.1137/0216051 .
• Пападимитриу, Христос (1994). Вычислительная сложность . Бостон: Аддисон-Уэсли . ISBN  978-0-201-53082-7 .

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

• Фортнау, Л.; Гасарч, В. «Вычислительная сложность» .
• Авиада Рубинштейна «Трудность аппроксимации между P и NP» , лауреата премии ACM года за докторскую диссертацию 2017 .
• «P против NP и зоопарк вычислительной сложности» . 26 августа 2014 г. Архивировано из оригинала 24 ноября 2021 г. – на YouTube .