Первая страница / Теория / Построение и анализ алгоритмов /

Класс проблем NP

Голосование: 13, 2

Введение

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

Кроме того, работы XX века в области математической логики показали, что существуют задачи, для решения которых теоретически не может существовать алгоритма. Классическим примером такой задачи является проблема останова: «Дан исходный код программы, требуется определить, остановится ли она за конечное время, если ее запустить».

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

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

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

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

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

Опишем формально машину Тьюринга. Далее в тексте будем использовать сокращение МТ.

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

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

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

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

Недетерминированная машина Тьюринга

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

Недетерминированная машина Тьюринга отличается от обычной (детерминированной) следующими правилами:

  • Для каждой пары (состояние, символ) определены несколько переходов.
  • НМТ выбирает любой переход.
  • Вход w допускается НМТ, если хотя бы одна последовательность переходов приводит НМТ к допускающему состоянию.

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

Принципиальная сложность, встающая при этом на пути, такова: соответствующая ДМТ может работать за экспоненциально большее время. Эту сложность человечество на данный момент так и не научилось обходить.

Проблема = язык

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

Рассмотрим какую-нибудь проблему, например «является ли данный граф связным?». Решить эту проблему — значит, привести алгоритм, принимающий на вход некоторую запись графа, и отвечающий «да» или «нет». Но действие алгоритма можно сформулировать и иначе: будем говорить, что данный алгоритм принимает язык записей связных графов.

Итак, пусть проблема имеет вид:

  • Принадлежит ли объект X множеству Y?
  • Обладает ли объект X свойством Y?

Будем формулировать проблему так:

  • Принадлежит ли запись объекта X языку Y?

Классы P и NP

Определение

Язык L принадлежит классу P, если существует ДМТ M, которая допускает язык L и останавливается за полиномиальное время.

Определение

Язык L принадлежит классу NP, если существует НМТ M, которая допускает язык L и останавливается за полиномиальное время.

Приведем пример языка, принадлежащего классу P

  • Язык записей графов, в которых есть эйлеров цикл.

Соответствующая ДМТ несложна: она проверяет связность данного графа, и проверяет, что степени всех вершин — четные. Если оба условия выполнены, ДМТ возвращает ответ «да».

Приведем пример языка, принадлежащего классу NP:

  • Язык записей графов, в которых есть гамильтонов цикл.

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

Поскольку всякая ДМТ является частным случаем НМТ, ясно, что

P in NP

Важнейшим неразрешенным вопросом для Computer Science до сих является: верно ли, что

PNP

Полиномиальное сведение

Предположим, что некоторый язык P1 не принадлежит классу P. То есть P1 — это некоторая заведомо сложная проблема.

Предположим также, что имеется некоторый язык P2, и все попытки построить алгоритм, решающий P2 не увенчались успехом. В таком случае, возникает предположение, что P2 не принадлежит P. Для доказательства этого предположения используем метод полиномиального сведения:

  • Найдем полиномиальный алгоритм, строящий по экземпляру P1 экземпляр P2 с таким же ответом (сведем P1 к P2).

После этого приведем доказательство от противного:

Пусть P2 принадлежит P. Тогда, по определению, существует ДМТ M, допускающая язык P2. Зная это, построим следующую ДМТ M′:

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

Эта ДМТ допускает язык P1. Язык P1 оказывается принадлежащим классу P. Получили противоречие, следовательно, P2 не принадлежит P, что и требовалось доказать.

Классы труднорешаемых проблем

Определение

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

Определение

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

Диаграмма Венна

Проблема SAT

Приведем пример очень важной для теории сложности NP–полной задачи. В англоязычной литературе для нее принято сокращение SAT (от англ. satisfiability — выполнимость), в русскоязычной, соответственно, ВЫП.

Пусть дана формула, содержащая булевы переменные, операторы «and» («и»), «or» («или») и «¬» («не»), и скобки. Формула называется выполнимой, если существует такой набор значений переменных, при подстановке которого формула принимает значение истина.

SAT — это язык выполнимых формул. В 1971 году Стивен Кук доказал NP–полноту задачи SAT.

Теорема (Кук)

Проблема SAT NP-полна.

Доказательство

Докажем сначала, что SAT is in NP.

Для этого достаточно привести недетерминированную машину Тьюринга, которая принимает язык SAT. Простейшая НМТ действует так:

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

Видно, что эта НМТ допускает формулу w тогда и только тогда, когда существует подстановка значений, выполняющая формулу w.

Рассмотрим любой язык Lиз NP. Необходимо теперь доказать, что существует полиномиальное сведение L к SAT, то есть по экземпляру Lпостроить формулу для SAT с тем же ответом. При этом, поскольку Lпринадлежит NP, существует НМТ M, которая допускает язык L, совершая не более p(n) переходов, где p(n) — некоторый полином.

Искомая формула имеет следующую структуру:

(М начинает, имея на входе данный экземпляр L) and
(Первый шаг M происходит по правилам) and
(…) and
(Шаг M номер p(n) происходит по правилам) and
(М пришло в допускающее состояние)

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

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

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

Проблема 3-SAT

Если некоторая проблема является NP–полной, то любое ее обобщение тем более является NP–полной проблемой. В то же время, иногда частный случай NP–полной проблемы может сам по себе обладать NP–полнотой. Важный пример — задача 3-SAT. Это задача о выполнимости некоторого класса булевых формул, но не столь общего, как в задаче SAT. Для определения 3-SAT введем несколько простых определений.

Литералом называется выражение вида «x» или «¬x», где x — переменная.

3-дизъюнктом называется выражение вида «a or b or c», где a, b и c — литералы.

Булева формула записана в 3-конъюнктивной нормальной форме, если она является логическим «и» произвольного количества 3-дизъюнктов. Например:

(x1 or ¬x2 or x3) andx1 or x2 or ¬x4) and (x2 or ¬x3 or x4)

Проблема 3-SAT формулируется так: является ли данная формула, записанная в 3-конъюнктивной нормальной форме, выполнимой.

Проблема 3-SAT также NP–полна, что чрезвычайно удобно использовать при доказательстве NP–полноты других задач.

Проблема IS

Следующая NP–полная проблема относится к теории графов. Сокращение IS расшифровывается как Independent Set — Независимое Множество, сокращенно — НМ.

Множество вершин графа называется независимым, если никакие две вершины из этого множества не соединены ребром.

Дан граф G и число k. Проблема IS такова: Существует ли в графе G независимое множество из k вершин?

Докажем NP–полноту проблемы IS.

Для начала убедимся, что IS is in NP. Для этого представим недетерминированный алгоритм, допускающий язык IS. Его суть такова:

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

Теперь сведем 3-SAT к IS, чем докажем NP-полноту IS. Для формулы в 3-конъюнктивной нормальной форме приведем граф и число, принадлежащие языку IS тогда и только тогда, когда формула принадлежит языку 3-SAT, то есть является выполнимой.

Каждому дизъюнкту в булевой формуле (например, (x1 or ¬x2 or x3)) поставим в соответствие 3 смежные вершины, по одной вершине на литерал. Тем самым мы потребуем, чтобы в решении задачи про независимое множество из этих вершин было выбрано не более одной.

Вершину, соответствующую литералу xi в одном дизъюнкте, и вершину, соответствующую литералу ¬xi в другом, соединим ребром. Тем самым мы удостоверимся, что в разных дизъюнктах не будут выбраны противоречащие друг другу литералы.

Положим k = количество дизъюнктов в формуле.

Поясним приведенные выше манипуляции на примере. Так выглядят формула и соответствующий ей граф (k = 3):

(x1or¬x2orx3)andx1orx2orx4)andx2or¬x3or¬x4)

Экземпляр задачи IS

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

Проблема 3-COL

Еще одна красивая NP–полная задача из теории графов относится к раскраске графа или определению хроматического числа графа.

Дан граф G. Можно ли раскрасить вершины G в три цвета так, чтобы не было двух смежных вершин, раскрашенных в один цвет?

Проблема 3-COL NP–полна, как и любая проблема k-COL при условии k ≥ 3.

Проблема ILP

Следующая NP–полная задача имеет алгебраический вид. Сокращение ILP расшифровывается как Integer Linear Programming — Целочисленное Линейное Программирование.

Дан набор ограничений вида

Неравенства-ограничения

При этом aiи c — целые числа.

Существует ли целочисленный вектор x, удовлетворяющий всем неравенствам?

Класс проблем co-NP

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

Дополнение языка L — это множество цепочек, не принадлежащих языку L.

Определение

Язык L принадлежит классу co-NP, если его дополнение принадлежит классу NP.

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

На данный момент в Computer Science открытым остается следующий вопрос: верно ли, что

NP ≠ co-NP

Возможно, для ответа на этот вопрос, удобно будет применить следующую теорему.

Теорема

NP = сo-NP тогда и только тогда, когда существует NP -полная задача, принадлежащая co-NP.

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

Диаграмма Венна

Источники

  1. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2002.
  2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2001.
  3. An Annotated List of Selected NP-complete Problems

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий