НП (сложность) - NP (complexity)

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Октябрь 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Нерешенная проблема в информатике: ${displaystyle {mathsf {P {overset {?} {=}} NP}}}$ (больше нерешенных проблем в информатике)

Диаграмма Эйлера за п, НП, НП-полный, и NP-жесткий множество проблем. В предположении, что P ≠ NP, существование проблем внутри NP, но вне обеих п и NP-Complete была установлен Ladner.^[1]

В теория сложности вычислений, НП (недетерминированное полиномиальное время) это класс сложности используется для классификации проблемы решения. НП - это набор проблем решения, для которых проблемные экземпляры, где ответ "да", есть доказательства проверяемый в полиномиальное время по детерминированная машина Тьюринга.^{[2][Примечание 1]}

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

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

Легко видеть, что класс сложности п (все проблемы, решаемые детерминированно за полиномиальное время) содержатся в NP (задачи, решения которых могут быть проверены за полиномиальное время), потому что, если проблема разрешима за полиномиальное время, то решение также можно проверить за полиномиальное время простым решением задачи . Но NP содержит гораздо больше проблем^{[Заметка 2]}, самые сложные из которых называются НП-полный проблемы. Алгоритм, решающий такую ​​задачу за полиномиальное время, также может решить любую другую задачу NP за полиномиальное время. Самое важное Проблема P против NP («P = NP?»), спрашивает, существуют ли алгоритмы с полиномиальным временем для решения NP-полных и, как следствие, всех NP задач. Широко распространено мнение, что это не так.^[4]

Класс сложности NP относится к классу сложности со-НП для которого ответ «нет» можно проверить за полиномиальное время. Является ли NP = co-NP - еще один нерешенный вопрос теории сложности.^[5]

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

Класс сложности NP можно определить в терминах NTIME следующее:

${displaystyle {mathsf {NP}} = igcup _ {kin mathbb {N}} {mathsf {NTIME}} (n ^ {k}).}$

куда ${displaystyle {mathsf {NTIME}} (n ^ {k})}$ это набор задач решения, которые могут быть решены недетерминированная машина Тьюринга в ${displaystyle O (n ^ {k})}$ время.

В качестве альтернативы NP можно определить с помощью детерминированных машин Тьюринга в качестве верификаторов. А язык L принадлежит NP тогда и только тогда, когда существуют многочлены п и q, и детерминированная машина Тьюринга M, так что

• Для всех Икс и у, машина M бежит во времени п(|Икс|) на входе ${displaystyle (x, y)}$
• Для всех Икс в L, существует строка у длины q(|Икс|) такие, что ${displaystyle M (x, y) = 1}$
• Для всех Икс не в L и все струны у длины q(|Икс|), ${displaystyle M (x, y) = 0}$

Фон

Много Информатика проблемы содержатся в NP, как и версии решений многих поиск и проблемы оптимизации.

Определение на основе верификатора

Чтобы объяснить определение NP на основе верификатора, рассмотрим проблема суммы подмножества: Предположим, что нам даны целые числа, {−7, −3, −2, 5, 8}, и мы хотим знать, равны ли некоторые из этих целых чисел нулю. Здесь ответ - «да», поскольку целые числа {−3, −2, 5} соответствуют сумме (−3) + (−2) + 5 = 0. Задача определения того, существует ли такое подмножество с нулевой суммой, называется проблема суммы подмножества.

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

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

Приведенный выше пример можно обобщить для любой задачи решения. Учитывая любой случай I проблемы ${displaystyle Pi}$ и свидетель W, если существует верификатор V, так что, учитывая упорядоченную пару (I, W) в качестве входных данных, V возвращает «да» за полиномиальное время, если свидетель докажет, что ответ «да» или «нет» за полиномиальное время в противном случае, тогда ${displaystyle Pi}$ находится в НП.

Версия этой проблемы с ответом «нет» сформулирована так: «Имеет ли каждое непустое подмножество ненулевую сумму при заданном конечном наборе целых чисел?». Определение NP на основе верификатора нет требуется эффективный верификатор для ответов «нет». Класс задач с такими верификаторами ответов «нет» называется co-NP. Фактически, это открытый вопрос, все ли задачи в NP также имеют верификаторы для ответов «нет» и, таким образом, находятся в совместной NP.

В некоторой литературе проверяющий называется «удостоверяющим», а свидетель - «свидетельство ".^[2]

Машинное определение

Эквивалентной определению, основанному на верификаторе, является следующая характеристика: NP - это класс проблемы решения решаемый недетерминированная машина Тьюринга что работает в полиномиальное время. То есть проблема решения ${displaystyle Pi}$ находится в NP всякий раз, когда ${displaystyle Pi}$ распознается некоторой недетерминированной машиной Тьюринга с полиномиальным временем ${displaystyle M}$ с экзистенциальное условие принятия, означающий, что ${displaystyle win Pi}$ тогда и только тогда, когда некоторый путь вычисления ${displaystyle M (w)}$ приводит к состоянию принятия. Это определение эквивалентно определению, основанному на верификаторе, потому что недетерминированная машина Тьюринга может решить проблему NP за полиномиальное время, недетерминированно выбрав сертификат и запустив верификатор на сертификате. Точно так же, если такая машина существует, то из нее естественным образом может быть построен верификатор с полиномиальным временем.

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

Характеристики

НП закрыт союз, пересечение, конкатенация, Клини звезда и разворот. Неизвестно, закрыта ли НП под дополнять (этот вопрос является так называемым вопросом "НП против совместной НП")

Почему некоторые проблемы НП трудно решить

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

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

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

Эквивалентность определений

Два определения NP как класса задач, решаемых недетерминированным Машина Тьюринга (TM) за полиномиальное время и класс задач, проверяемых детерминированной машиной Тьюринга за полиномиальное время, эквивалентны. Доказательство описано во многих учебниках, например, в книге Сипсера. Введение в теорию вычислений, раздел 7.3.

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

И наоборот, предположим, что у нас есть недетерминированная ТМ с именем A, принимающая данный язык L. На каждом из полиномиально многих шагов машина дерево вычислений разветвляется не более чем в конечном числе направлений. Должен быть хотя бы один принимающий путь, и строка, описывающая этот путь, является доказательством, предоставленным верификатору. Затем верификатор может детерминированно моделировать A, следуя только принимающему пути и проверяя, что он принимает в конце. Если A отклоняет ввод, путь для принятия отсутствует, и проверяющий всегда будет отклонять.

Отношение к другим классам

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

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

NP определяется с использованием только детерминированных машин. Если мы позволим верификатору быть вероятностным (это, однако, не обязательно машина BPP^[6]) получаем класс MA решается с помощью Протокол Артура-Мерлина без связи Артура с Мерлином.

NP - это класс проблемы решения; аналогичный класс функциональных задач ФНП.

Единственные известные строгие включения произошли от теорема об иерархии времени и теорема пространственной иерархии, и соответственно они ${displaystyle {mathsf {NPsubsetneq NEXPTIME}}}$ и ${displaystyle {mathsf {NPsubsetneq EXPSPACE}}}$.

Другие характеристики

С точки зрения описательная теория сложности, NP точно соответствует множеству языков, определяемых экзистенциальным логика второго порядка (Теорема Феджина ).

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

Главный результат теории сложности состоит в том, что NP можно охарактеризовать как проблемы, решаемые с помощью вероятностно проверяемые доказательства где проверяющий использует O (log п) случайные биты и проверяет только постоянное количество бит строки доказательства (класс PCP(бревно п, 1)). Говоря более неформально, это означает, что описанный выше NP-верификатор может быть заменен на тот, который просто «выборочно проверяет» несколько мест в строке доказательств, и использование ограниченного количества подбрасываний монеты может определить правильный ответ с высокой вероятностью. Это позволяет получить несколько результатов о твердости аппроксимационные алгоритмы быть доказанным.

Пример

Это список некоторых проблем, которые есть в NP:

Все проблемы в п, обозначенный ${displaystyle {mathsf {Psubseteq NP}}}$. Имея справку о проблеме в п, мы можем игнорировать сертификат и просто решить проблему за полиномиальное время.

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

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

А недетерминированная машина Тьюринга найти такой маршрут можно следующим образом:

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

Можно думать о каждой догадке как о "разветвление "новая копия машины Тьюринга, которая будет следовать по каждому из возможных путей вперед, и если хотя бы одна машина найдет маршрут на расстоянии меньше, чем k, эта машина принимает ввод. (Эквивалентно, это можно рассматривать как одну машину Тьюринга, которая всегда правильно угадывает)

А бинарный поиск на диапазоне возможных расстояний может преобразовать версию решения Коммивояжера в версию оптимизации, повторно вызывая версию решения (полиномиальное количество раз).^{[нужна цитата ]}

Вариант решения проблемы проблема целочисленной факторизации: данные целые числа п и k, есть ли фактор ж с 1 < ж < k и ж разделение п?^{[нужна цитата ]}

В Проблема изоморфизма подграфов определения того, является ли график грамм содержит подграф, изоморфный графу ЧАС.

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

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

• Машина Тьюринга

Примечания

Рекомендации

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

• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7. Раздел 34.2: Проверка с полиномиальным временем, стр. 979–983.
• Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. ISBN  0-534-94728-X. Разделы 7.3–7.5 (Класс NP, NP-полнота, Дополнительные NP-полные задачи), стр. 241–271.
• Дэвид Харел, Ишай Фельдман. Алгоритмика: Дух вычислений, Addison-Wesley, Reading, MA, 3-е издание, 2004 г.

внешняя ссылка

• Зоопарк сложности: НП
• Американский ученый учебник по традиционным и новейшим исследованиям теории сложности: «Случайные алгоритмы»