NP — это класс языков, которые имеют верификаторы полиномиального времени.
Класс NP, обозначающий «недетерминированное полиномиальное время», является фундаментальным понятием теории сложности вычислений, раздела теоретической информатики. Чтобы понять NP, нужно сначала уловить понятие проблем принятия решений, которые представляют собой вопросы с ответом «да» или «нет». Язык в этом контексте относится к набору строк в некотором алфавите, где каждая строка кодирует экземпляр проблемы принятия решения.
Говорят, что язык (L) находится в NP, если существует полиномиальный верификатор для (L). Верификатор — это детерминированный алгоритм (V), который принимает два входных параметра: экземпляр (x) и сертификат (y). Сертификат (y) также известен как «свидетель» или «доказательство». Верификатор (V) проверяет, подтверждает ли сертификат (y) принадлежность (x) языку (L). Формально язык (L) находится в NP, если существует алгоритм с полиномиальным временем (V) и полином (p(n)) такие, что для каждой строки (x в L) существует строка (y) с ( |y| leq p(|x|)) и (V(x, y) = 1). И наоборот, для каждой строки (x не в L) не существует строки (y) такой, что (V(x, y) = 1).
Чтобы пояснить эту концепцию, рассмотрим хорошо известную проблему «булевой выполнимости» (SAT). Задача SAT спрашивает, существует ли присвоение значений истинности переменным в данной логической формуле, при котором формула оценивается как истина. Проблема SAT находится в NP, потому что, учитывая булеву формулу (фи) и присвоение (альфа) значений истинности ее переменным, можно за полиномиальное время проверить, удовлетворяет ли (альфа) (фи). Здесь экземпляр ( x ) — это булева формула ( phi ), а сертификат ( y ) — это присвоение ( альфа ). Верификатор (V) проверяет, делает ли (alpha) (phi) истинным, что можно сделать за полиномиальное время относительно размера (phi).
Еще один показательный пример — задача «гамильтонов путь». Эта задача спрашивает, существует ли в данном графе путь, который посещает каждую вершину ровно один раз. Проблема гамильтонового пути также находится в NP, потому что, учитывая граф (G) и последовательность вершин (P), можно за полиномиальное время проверить, является ли (P) гамильтоновым путем в (G). В этом случае экземпляр (x) — это граф (G), а сертификат (y) — это последовательность вершин (P). Верификатор (V) проверяет, образует ли (P) гамильтонов путь, что можно сделать за полиномиальное время относительно размера (G).
Концепция проверяемости за полиномиальное время важна, поскольку она дает способ характеризовать проблемы, которые можно эффективно проверить, даже если поиск решения может быть вычислительно невозможен. Это приводит к известному вопросу о том, (P = NP), который спрашивает, может ли каждая проблема, решение которой можно проверить за полиномиальное время, быть также решена за полиномиальное время. Класс (P) состоит из задач принятия решений, которые можно решить за полиномиальное время с помощью детерминированной машины Тьюринга. Если (P = NP), это будет означать, что каждая задача с верификатором за полиномиальное время также имеет решатель за полиномиальное время. Этот вопрос остается одной из самых важных открытых проблем в информатике.
Одним из ключевых свойств NP является то, что он замкнут при полиномиальных редукциях. Сведение за полиномиальное время от языка ( L_1 ) к языку ( L_2 ) — это вычислимая функция за полиномиальное время ( f ), такая что ( x в L_1 ) тогда и только тогда, когда ( f(x) в L_2 ). Если существует полиномиальное сокращение времени от ( L_1 ) до ( L_2 ) и ( L_2 ) находится в NP, то ( L_1 ) также находится в NP. Это свойство способствует изучению NP-полноты, которая выявляет «самые сложные» проблемы в NP. Задача называется NP-полной, если она находится в NP и каждую задачу из NP можно свести к ней за полиномиальное время. Задача SAT была первой проблемой, NP-полнота которой была доказана, и она служит основой для доказательства NP-полноты других задач.
Чтобы дополнительно проиллюстрировать концепцию проверяемости за полиномиальное время, рассмотрим задачу «Сумма подмножества». Эта задача спрашивает, существует ли подмножество данного набора целых чисел, сумма которого равна указанному целевому значению. Проблема суммы подмножества находится в NP, потому что, учитывая набор целых чисел ( S ), целевое значение ( t ) и подмножество ( S' ) из ( S ), можно проверить за полиномиальное время, является ли сумма элементов в (S') равно (t). Здесь экземпляр (x) — это пара ((S, t)), а сертификат (y) — это подмножество (S'). Верификатор (V) проверяет, равна ли сумма элементов в (S') (t), что можно сделать за полиномиальное время относительно размера (S).
Важность полиномиальной проверяемости выходит за рамки теоретических соображений. На практике это означает, что для задач в NP, если предложенное решение (сертификат) предоставлено, его можно эффективно проверить. Это имеет значительные последствия для криптографических протоколов, задач оптимизации и различных областей, где важна проверка правильности решения.
Подводя итог, класс NP включает в себя проблемы принятия решений, для которых предлагаемое решение может быть проверено за полиномиальное время с помощью детерминированного алгоритма. Эта концепция лежит в основе теории сложности вычислений и имеет глубокие последствия как для теоретических, так и для практических аспектов информатики. Изучение NP, проверяемости за полиномиальное время и связанных с ними концепций, таких как NP-полнота, продолжает оставаться динамичной и важной областью исследований.
Другие недавние вопросы и ответы, касающиеся Многогранность:
- Класс PSPACE не равен классу EXPSPACE?
- Является ли класс сложности P подмножеством класса PSPACE?
- Можем ли мы доказать, что классы Np и P совпадают, найдя эффективное полиномиальное решение для любой NP-полной задачи в детерминированной TM?
- Может ли класс NP быть равен классу EXPTIME?
- Есть ли в PSPACE проблемы, для которых не существует известного алгоритма NP?
- Может ли проблема SAT быть полной NP-проблемой?
- Может ли проблема относиться к классу сложности NP, если существует недетерминированная машина Тьюринга, которая решит ее за полиномиальное время?
- Являются ли P и NP на самом деле одним и тем же классом сложности?
- Каждый ли контекстно-свободный язык относится к классу сложности P?
- Существует ли противоречие между определением NP как класса задач решения с верификаторами с полиномиальным временем и тем фактом, что проблемы в классе P также имеют верификаторы с полиномиальным временем?
Посмотреть больше вопросов и ответов в категории Сложность