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

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

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

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

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

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

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

Пример [ править ]

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

История [ править ]

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

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

Контекст [ править ]

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

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

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

Является ли P равняться NP ?

С 2002 года Уильям Гасарх провел три опроса исследователей по этому и смежным вопросам. ^{[9] [10] [11]} Уверенность в том, что P  ≠  NP растет - в 2019 году 88% полагали, что P  ≠  NP , по сравнению с 83% в 2012 году и 61% в 2002 году. Если ограничиться экспертами, ответы 2019 года стали 99% верят P  ≠  NP . ^[11]

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 примет? ^[12] Это в NP, потому что (учитывая ввод) просто проверить, принимает ли M ввод, моделируя M ; он является NP- полным, потому что верификатор для любого конкретного случая проблемы в NP может быть закодирован как машина полиномиального времени Mчто требует проверки решения в качестве входных данных. Тогда вопрос о том, является ли экземпляр экземпляром «да» или «нет», определяется тем, существует ли допустимый ввод.

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

Более сложные проблемы [ править ]

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

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

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

Проблемы в NP не известны ни в P, ни в NP-Complete [ править ]

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

Проблема изоморфизма графов является вычислительной задачей определения , является ли две конечными графами являются изоморфными . Важная нерешенная проблема в теории сложности , является ли проблема изоморфизма графов в P , NP -полных, или НП -intermediate. Ответ неизвестен, но считается, что проблема как минимум не NP- неполная. ^[20] Если изоморфизм графов является NP- полным, иерархия полиномиального времени схлопывается до второго уровня. ^[21]Поскольку широко распространено мнение, что иерархия полиномов не коллапсирует до какого-либо конечного уровня, считается, что изоморфизм графов не является NP- полным. Лучший алгоритм для этой проблемы, созданный Ласло Бабаем и Юджином Люксом , имеет время выполнения 2 ^{O ( √ n log n )} для графов с n вершинами.

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

${\ displaystyle 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 означает "легкий"? [ редактировать ]

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

Во-первых, на практике это не всегда так. Теоретический полиномиальный алгоритм может иметь чрезвычайно большие постоянные коэффициенты или показатели, что делает его непрактичным. Например, задача о решении ли граф G содержит H как минор , где Н является фиксированным, может быть решена в рабочее время O ( п ² ), ^[24] , где п есть число вершин в G . Тем не менее, большое обозначение вывода скрывает константу, зависящую от сверхэкспоненциально H . Константа больше чем (с использованием обозначения Кнута со стрелкой вверх${\ displaystyle 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (h / 2)))}$), И где ч есть число вершин в H . ^[25]

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

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

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

Согласно опросам ^{[9] [27]} большинство компьютерных ученых считают, что P  ≠  NP . Основная причина этого убеждения состоит в том, что после десятилетий изучения этих проблем никто не смог найти алгоритм с полиномиальным временем для любой из более чем 3000 важных известных NP- полных задач (см. Список NP- полных задач ). Эти алгоритмы искали задолго до того, как была даже определена концепция NP- полноты ( 21 NP- полная задача Карпа , среди первых найденных, были хорошо известными существующими проблемами в то время, когда они были показаны как NP- полные). Кроме того, результатP = NP будет означать множество других поразительных результатов, которые в настоящее время считаются ложными, например NP = co-NP и P = PH .

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

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

-  Скотт Ааронсон , UT Остин

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

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

-  Моше Варди , Университет Райса

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

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

Последствия решения [ править ]

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

P = NP [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

P ≠ NP [ править ]

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

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

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

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

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

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

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

Заявленные решения [ редактировать ]

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

Логические характеристики [ править ]

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

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

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

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

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

// Алгоритм, принимающий NP- полный язык SUBSET-SUM. // // это алгоритм с полиномиальным временем тогда и только тогда, когда P = NP . // // «Полиномиальное время» означает, что он возвращает «да» в полиномиальное время, // когда ответ должен быть «да», и выполняется бесконечно, если он равен «нет». // // Ввод: S = конечный набор целых чисел // Вывод: «да», если какое-либо подмножество S складывается до 0. // В противном случае выполняется бесконечно без вывода. // Примечание: «Номер программы M» - это программа, полученная // записью целого числа M в двоичном формате, а затем // рассмотрением этой строки битов как // программы. Каждая возможная программа может быть// генерируется таким образом, хотя большинство из них // ничего не делают из-за синтаксических ошибок.ДЛЯ K = 1 ... ∞ ДЛЯ M = 1 ... K Выполните программу номер M для K шагов с входом S ЕСЛИ программа выводит список различных целых чисел И все целые числа находятся в S И сумма целых чисел равна 0 ТОГДА ВЫВОД «да» и HALT

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

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

Формальные определения [ править ]

P и NP [ править ]

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

${\ displaystyle \ mathbf {P} = \ {L: L = L (M) {\ text {для некоторой детерминированной машины Тьюринга с полиномиальным временем}} M \}}$

куда

${\ Displaystyle L (M) = \ {ш \ in \ Sigma ^ {*}: M {\ text {принимает}} ш \}}$

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

1. M останавливается на всех входах w и
2. существует такое, что , где O относится к нотации большого O и${\ displaystyle k \ in N}$${\ Displaystyle Т_ {М} (п) \ в О (п ^ {к})}$

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

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

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

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

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

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

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

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

Пример [ править ]

Позволять

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

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

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

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

NP-полнота [ править ]

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

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

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

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

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

Популярная культура [ править ]

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

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

• Fortnow, L .; Gasarch, W. "Вычислительная сложность" .
• Работа Авиада Рубинштейна « Трудность приближения между P и NP» , лауреат премии ACM за докторскую диссертацию в 2017 году .
• «P против NP и зоопарк вычислительной сложности» . 26 августа 2014 г. - через YouTube .