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

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

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

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

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

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

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

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

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

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

Пример

Рассмотрим следующую задачу типа «да/нет»: дана неполная сетка судоку размера , существует ли хотя бы одно допустимое решение, в котором каждая строка, столбец и квадрат содержат целые числа от 1 до ? Легко проверить примеры «да» этой обобщенной задачи судоку, если задано возможное решение. Однако неизвестно, существует ли алгоритм с полиномиальным временем, который может правильно ответить «да» или «нет» на все примеры этой задачи. Следовательно, обобщенная задача судоку относится к NP (быстро проверяемая), но может относиться или не относиться к P (быстро решаемая). (Необходимо рассмотреть обобщенную версию судоку, поскольку любая фиксированная сетка судоку имеет только конечное число возможных сеток. В этом случае задача относится к P, поскольку ответ можно найти с помощью поиска по таблице.) ${\displaystyle n^{2}\times n^{2}}$ ${\displaystyle n\times n}$ ${\displaystyle n^{2}}$

История

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

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

Контекст

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

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

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

Равно ли P и NP?

С 2002 года Уильям Гасарч провел три опроса исследователей по этому и связанным с ним вопросам. ^{[8] [9] [10]} Уверенность в том, что P ≠ NP, растет — в 2019 году 88% считали, что P ≠ NP, по сравнению с 83% в 2012 году и 61% в 2002 году. Если ограничиться экспертами, то в 2019 году ответы стали 99% считать, что P ≠ NP. ^[10] Эти опросы не подразумевают, что 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 ? ^[11] Он находится в NP, потому что (при наличии входных данных) просто проверить, принимает ли M входные данные, смоделировав M ; он является NP-полным, потому что верификатор для любого конкретного примера задачи в NP может быть закодирован как полиномиальная машина M , которая принимает проверяемое решение в качестве входных данных. Тогда вопрос о том, является ли пример экземпляром «да» или «нет», определяется тем, существуют ли допустимые входные данные.

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

Более сложные проблемы

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

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

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

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

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

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

Задача факторизации целых чисел — это вычислительная задача определения простого фактора заданного целого числа. Формулируя ее как задачу принятия решений, это задача определения, имеет ли входной фактор фактор меньше k . Эффективный алгоритм факторизации целых чисел неизвестен, и этот факт лежит в основе нескольких современных криптографических систем, таких как алгоритм RSA . Задача факторизации целых чисел находится в NP и в co-NP (и даже в UP и co-UP ^[23] ). Если задача является NP-полной, иерархия полиномиального времени схлопнется до своего первого уровня (т. е. NP = co-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 «легко»?

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

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

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

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

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

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

Кук дает переформулировку проблемы в The P Versus NP Problem как «Does P = NP?» ^[28] Согласно опросам, ^{[8] [29]} большинство компьютерных специалистов считают, что P ≠ NP. Ключевой причиной этого убеждения является то, что после десятилетий изучения этих проблем никто не смог найти алгоритм полиномиального времени для любой из более чем 3000 важных известных NP-полных проблем (см. Список NP-полных проблем ). Эти алгоритмы искали задолго до того, как была определена концепция NP-полноты ( 21 NP-полная проблема Карпа , среди первых найденных, были хорошо известными существующими проблемами в то время, когда было показано, что они NP-полны). Более того, результат P = NP подразумевал бы множество других поразительных результатов, которые в настоящее время считаются ложными, например, NP =  co-NP и P =  PH .

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

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

—  Скотт Ааронсон , Юта Остин

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

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

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

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

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

DLIN против NLIN

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

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

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

П = НП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

П ≠ НП

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

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

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

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

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

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

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

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

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

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

Аналогично, NP — это множество языков, выражаемых в экзистенциальной логике второго порядка , то есть логике второго порядка, ограниченной для исключения универсальной квантификации по отношениям, функциям и подмножествам. Языки в полиномиальной иерархии PH соответствуют всей логике второго порядка. Таким образом, вопрос «является ли P собственным подмножеством NP» можно переформулировать как «способна ли экзистенциальная логика второго порядка описывать языки (конечных линейно упорядоченных структур с нетривиальной сигнатурой), которые не может описать логика первого порядка с наименьшим числом неподвижных точек?». ^[47] Слово «экзистенциальный» можно даже опустить из предыдущей характеристики, поскольку 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 в двоичном виде, а затем // рассмотрения этой строки битов как // программы. Каждая возможная программа может быть // сгенерирована таким образом, хотя большинство ничего // не делает из-за синтаксических ошибок.ДЛЯ К = 1...∞ ДЛЯ М = 1...К Запустить программу номер M на K шагов с входным сигналом S ЕСЛИ программа выводит список различных целых чисел И все целые числа находятся в S И целые числа в сумме дают 0 ЗАТЕМ ВЫВОД "да" и ОСТАНОВКА

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

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

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

П и НП

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

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

где

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

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

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

${\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 — это набор языков с конечным алфавитом и верификатором, который выполняется за полиномиальное время. Ниже дано определение «верификатора»:

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

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

1. Для всех таких , что ( x , y ) ∈ 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 , а y, такой что ( x , y ) ∈ R, называется сертификатом принадлежности x к L.

Не все верификаторы должны быть полиномиальными по времени. Однако для того, чтобы 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\}.}$

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

COMPOSITE также случайно оказывается в P, факт, продемонстрированный изобретением теста на простоту AKS . ^[48]

NP-полнота

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

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

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

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

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

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

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

Массовая культура

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

В шестом эпизоде ​​седьмого сезона « Симпсонов » « Treehouse of Horror VI » уравнение P = NP появляется вскоре после того, как Гомер случайно попадает в «третье измерение». ^{[53] [54]}

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

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

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

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

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

Примечания

1. Недетерминированная машина Тьюринга может перейти в состояние, которое не определяется предыдущим состоянием. Такая машина могла бы решить задачу NP за полиномиальное время, попадая в состояние правильного ответа (по счастливой случайности), а затем традиционно проверяя его. Такие машины непрактичны для решения реалистичных задач, но могут использоваться в качестве теоретических моделей.
2. Насколько эффективным должно быть решение, чтобы представлять угрозу криптографии, зависит от деталей. Решение с разумным постоянным членом было бы катастрофическим. С другой стороны, решение, которое почти во всех случаях не будет представлять непосредственной практической опасности. ${\displaystyle O(N^{2})}$ ${\displaystyle \Omega (N^{4})}$

Ссылки

1. Fortnow, Lance (2009). "The status of the P versus NP problem" (PDF) . Communications of the ACM . 52 (9): 78–86. CiteSeerX  10.1.1.156.767 . doi :10.1145/1562164.1562186. S2CID  5969255. Архивировано из оригинала (PDF) 24 февраля 2011 г. . Получено 26 января 2010 г. .
2. Фортнау, Лэнс (2013). Золотой билет: P, NP и поиск невозможного . Принстон, Нью-Джерси: Princeton University Press. ISBN 9780691156491.
3. Кук, Стивен (1971). «Сложность процедур доказательства теорем». Труды Третьего ежегодного симпозиума ACM по теории вычислений . С. 151–158. doi :10.1145/800157.805047. ISBN 9781450374644. S2CID  7573663.
4. Л. А. Левин (1973). Универсальные задачи передачи. Пробл. передача информ . 9 (3): 115–116.
5. NSA (2012). «Письма Джона Нэша» (PDF) . Архивировано (PDF) из оригинала 9 ноября 2018 года.
6. Хартманис, Юрис. "Гёдель, фон Нейман и проблема P = NP" (PDF) . Бюллетень Европейской ассоциации теоретической информатики . 38 : 101–107.
7. Сипсер, Майкл: Введение в теорию вычислений, второе издание, международное издание , стр. 270. Thomson Course Technology, 2006. Определение 7.19 и теорема 7.20.
8. William I. Gasarch (июнь 2002 г.). "The P=?NP poll" (PDF) . SIGACT News . 33 (2): 34–47. CiteSeerX 10.1.1.172.1005 . doi :10.1145/564585.564599. S2CID  36828694. Архивировано (PDF) из оригинала 15 июня 2007 г. 
9. Уильям И. Гасарч . "Второй опрос P=?NP" (PDF) . Новости SIGACT . 74. Архивировано (PDF) из оригинала 24 января 2014 г.
10. "Guest Column: The Third P =? NP Poll1" (PDF) . Архивировано (PDF) из оригинала 31 марта 2019 г. . Получено 25 мая 2020 г. .
11. Скотт Ааронсон. "PHYS771 Лекция 6: P, NP и друзья" . Получено 27 августа 2007 г.
12. "Курс магистратуры: Основы компьютерных наук". www.cs.ox.ac.uk . Получено 25 мая 2020 г. .
13. Колборн, Чарльз Дж. (1984). «Сложность завершения частичных латинских квадратов». Дискретная прикладная математика . 8 (1): 25–30. doi : 10.1016/0166-218X(84)90075-1 .
14. И. Холиер (1981). «NP-полнота некоторых задач разбиения ребер». SIAM J. Comput . 10 (4): 713–717. doi :10.1137/0210054.
15. Авиезри Френкель и Д. Лихтенштейн (1981). «Вычисление идеальной стратегии для шахмат n × n требует времени, экспоненциального по n ». Журнал комбинаторной теории . Серия A. 31 (2): 199–214. doi :10.1016/0097-3165(81)90016-9.
16. Дэвид Эппштейн . «Вычислительная сложность игр и головоломок».
17. Фишер, Майкл Дж .; Рабин, Майкл О. (1974). «Суперэкспоненциальная сложность арифметики Пресбургера». Труды симпозиума SIAM-AMS по прикладной математике . 7 : 27–41. Архивировано из оригинала 15 сентября 2006 г. Получено 15 октября 2017 г.
18. Валиант, Лесли Г. (1979). «Сложность проблем перечисления и надежности». Журнал SIAM по вычислениям . 8 (3): 410–421. doi :10.1137/0208032.
19. Ladner, RE (1975). «О структуре полиномиальной приводимости по времени». Журнал ACM . 22 : 151–171 См. следствие 1.1. doi : 10.1145/321864.321877 . S2CID  14352974.
20. Арвинд, Викраман; Курур, Пиюш П. (2006). «Изоморфизм графов есть в SPP». Информация и вычисления . 204 (5): 835–852. doi :10.1016/j.ic.2006.02.002.
21. Шёнинг, Уве (1988). «Изоморфизм графов находится в низкой иерархии». Журнал компьютерных и системных наук . 37 (3): 312–323. doi :10.1016/0022-0000(88)90010-4.
22. Бабай, Ласло (2018). «Группа, графы, алгоритмы: проблема изоморфизма графов». Труды Международного конгресса математиков — Рио-де-Жанейро 2018. Том IV. Приглашенные лекции . World Sci. Publ., Хакенсак, Нью-Джерси. С. 3319–3336. MR  3966534.
23. Лэнс Фортнау . Блог о сложности вычислений: Класс сложности недели: Факторизация. 13 сентября 2002 г.
24. Писингер, Д. 2003. «Где трудные задачи о рюкзаке?» Технический отчет 2003/08, Кафедра компьютерных наук, Копенгагенский университет, Копенгаген, Дания
25. Каварабаяси, Кен-ичи; Кобаяси, Юсукэ; Рид, Брюс (2012). «Проблема непересекающихся путей за квадратичное время». Журнал комбинаторной теории . Серия B. 102 (2): 424–435. doi : 10.1016/j.jctb.2011.07.004 .
26. Джонсон, Дэвид С. (1987). «Столбец NP-полноты: постоянное руководство (издание 19)». Журнал алгоритмов . 8 (2): 285–303. CiteSeerX 10.1.1.114.3864 . doi :10.1016/0196-6774(87)90043-5. 
27. Gondzio, Jacek; Terlaky, Tamás (1996). "3 Вычислительный взгляд на методы внутренней точки". В JE Beasley (ред.). Advances in linear and integer programming . Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. pp. 103–144. MR  1438311. Файл Postscript на веб-сайте Gondzio и на веб-сайте McMaster University Terlaky.
28. Кук, Стивен (апрель 2000 г.). "Проблема P против NP" (PDF) . Clay Mathematics Institute . Архивировано (PDF) из оригинала 16 декабря 2013 г. . Получено 18 октября 2006 г. .
29. Розенбергер, Джек (май 2012). "Результаты опроса P против NP". Сообщения ACM . 55 (5): 10.
30. Скотт Ааронсон (4 сентября 2006 г.). «Причины верить»., пункт 9.
31. Балькасар, Хосе Луис; Диас, Хосеп; Габарро, Хоаким (1990). Структурная сложность II . Спрингер Верлаг. ISBN 3-540-52079-1., Теорема 3.9
32. См. Хори, С.; Ватанабэ, О. (1997). "Генерация жестких экземпляров для SAT". Алгоритмы и вычисления . Конспект лекций по информатике. Том 1350. Springer. стр. 22–31. arXiv : cs/9809117 . Bibcode :1998cs........9117H. doi :10.1007/3-540-63890-3_4. ISBN 978-3-540-63890-2.для сокращения факторизации до SAT. 512-битная задача факторизации (8400 MIPS-лет при факторизации) переводится в задачу SAT из 63 652 переменных и 406 860 предложений.
33. См., например, Massacci, F.; Marraro, L. (2000). «Логический криптоанализ как проблема SAT». Journal of Automated Reasoning . 24 (1): 165–203. CiteSeerX 10.1.1.104.962 . doi :10.1023/A:1006326723002. S2CID  3114247. в котором экземпляр DES кодируется как задача SAT с 10336 переменными и 61935 предложениями. Экземпляр задачи 3DES будет примерно в 3 раза больше этого размера.
34. Де, Дебапратим; Кумарасубраманиан, Абишек; Венкатесан, Рамаратнам (2007). «Инверсионные атаки на защищенные хэш-функции с использованием решателей SAT». Теория и применение тестирования выполнимости – SAT 2007. Международная конференция по теории и применению тестирования выполнимости. Springer. стр. 377–382. doi :10.1007/978-3-540-72788-0_36.
35. Бергер, Б.; Лейтон , Т. (1998). «Сворачивание белка в гидрофобно-гидрофильной (HP) модели является NP-полным». J. Comput. Biol . 5 (1): 27–40. CiteSeerX 10.1.1.139.5547 . doi :10.1089/cmb.1998.5.27. PMID  9541869. 
36. История этого письма и его перевод от Sipser, Michael. "История и статус вопроса P против NP" (PDF) . Архивировано (PDF) из оригинала 2 февраля 2014 г.
37. Джонсон, Дэвид С. (август 2012 г.). «Краткая история NP-полноты, 1954–2012». В Grötschel, M. (ред.). Истории оптимизации (PDF) . Documenta Mathematica. стр. 359–376. ISBN 978-3-936609-58-5. ISSN  1431-0643.
38. Кнут, Дональд Э. (20 мая 2014 г.). Двадцать вопросов Дональду Кнуту. InformIT . Получено 20 июля 2014 г.
39. LR Foulds (октябрь 1983 г.). «Эвристический подход к решению проблем». Журнал общества операционных исследований . 34 (10): 927–934. doi :10.2307/2580891. JSTOR  2580891.
40. Р. Импальяццо, «Личный взгляд на сложность в среднем случае», стр. 134, 10-я ежегодная конференция по структуре в теории сложности (SCT'95), 1995.
41. "Предварительная программа семинара "Сложность и криптография: статус миров Импальяццо"". Архивировано из оригинала 15 ноября 2013 г.
42. TP Baker; J. Gill; R. Solovay (1975). «Релятивизации вопроса P =? NP». SIAM Journal on Computing . 4 (4): 431–442. doi :10.1137/0204037.
43. Разборов, Александр А.; Стивен Рудич (1997). «Естественные доказательства». Журнал компьютерных и системных наук . 55 (1): 24–35. doi : 10.1006/jcss.1997.1494 .
44. S. Aaronson; A. Wigderson (2008). Algebrization: A New Barrier in Complexity Theory (PDF) . Proceedings of ACM STOC'2008. pp. 731–740. doi :10.1145/1374376.1374481. Архивировано (PDF) из оригинала 21 февраля 2008 г.
45. Ааронсон, Скотт . «Является ли P против NP формально независимым?» (PDF) . Архивировано (PDF) из оригинала 16 января 2017 г..
46. Бен-Давид, Шай; Халеви, Шай (1992). О независимости P от NP. Технион (Технический отчет). Том 714. Архивировано из оригинала (GZIP) 2 марта 2012 г..
47. Эльвира Майордомо. «P против NP». Архивировано 16 февраля 2012 года в Wayback Machine Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).
48. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . JSTOR  3597229. Архивировано (PDF) из оригинала 26 сентября 2006 г.
49. Джон Маркофф (8 октября 2009 г.). «Призы в сторону, головоломка P-NP имеет последствия». The New York Times .
50. Герхард Дж. Вёгингер . "Страница P-против-NP" . Получено 24 июня 2018 г.
51. Маркофф, Джон (16 августа 2010 г.). «Шаг 1: Опубликуйте неуловимое доказательство. Шаг 2: Посмотрите фейерверк». The New York Times . Получено 20 сентября 2010 г.
52. Geere, Duncan (26 апреля 2012 г.). «Фильм «Коммивояжер» рассматривает последствия, если P равно NP». Wired UK . Получено 26 апреля 2012 г.
53. Хардести, Ларри (29 октября 2009 г.). «Объяснение: P против NP».
54. Шадиа, Аджам (13 сентября 2013 г.). «Что такое проблема P против NP? Почему она важна?».
55. Газарч, Уильям (7 октября 2013 г.). «P против NP элементарен? Нет — P против NP элементарен». blog.computationalcomplexity.org . Получено 6 июля 2018 г.
56. Киркпатрик, Ноэль (4 октября 2013 г.). "Elementary Solve for X Review: Sines of Murder". TV.com . Получено 6 июля 2018 г. .
57. Wigderson, Avi (2019). Математика и вычисления: теория, революционизирующая технологию и науку . Princeton University Press. ISBN 978-0-691-18913-0.
58. LG Valiant. Классы полноты в алгебре. В трудах 11-го ACM STOC, стр. 249–261, 1979.

Источники

• Рейчел Кроуэлл (28 мая 2021 г.). «Главные нерешенные вопросы математики остаются в основном загадочными. Решена только одна из семи задач Премии тысячелетия, названных 21 год назад». www. scientificamerican.com . Получено 21 июня 2021 г. Эта проблема касается вопроса о том, имеют ли вопросы, которые легко проверить (класс запросов, называемый NP), также решения, которые легко найти (класс, называемый P).
• Hosch, William L (11 августа 2009 г.). «P против NP-задачи по математике». Encyclopaedia Britannica . Получено 20 июня 2021 г. .
• "P vs NP Problem". www.claymath.org (Кук, Левин) . Получено 20 июня 2021 г. Предположим, что вы организуете размещение в общежитии для группы из четырехсот студентов университета. Количество мест ограничено, и только сто студентов получат места в общежитии. Чтобы усложнить ситуацию, декан предоставил вам список пар несовместимых студентов и попросил, чтобы ни одна пара из этого списка не фигурировала в вашем окончательном выборе. Это пример того, что специалисты по информатике называют NP-задачей...

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

• Кормен, Томас (2001). Введение в алгоритмы . Кембридж: MIT Press . ISBN 978-0-262-03293-3.
• Garey, Michael R .; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR  0519066. OCLC  247570676.
• Goldreich, Oded (2010). P, NP и NP-полнота . Кембридж: Cambridge University Press . ISBN 978-0-521-12254-2.Онлайн-черновики
• Иммерман, Нил (1987). «Языки, захватывающие классы сложности». Журнал SIAM по вычислениям . 16 (4): 760–778. CiteSeerX  10.1.1.75.3035 . doi :10.1137/0216051.
• Пападимитриу, Христос (1994). Computational Complexity . Бостон: Addison-Wesley . ISBN 978-0-201-53082-7.

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

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