NP-полные задачи

Размещено на http://www.allbest.ru/

Введение

Большинство задач, интересных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы решения. То есть время работы алгоритма на входе длины n составляет не более O(n^k) для некоторой константы k (не зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классический пример такой задачи - «проблема остановки» (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» - время его работы не есть O(n^k) ни для какого фиксированного числа k.

Если мы хотим провести пусть грубую, но формальную границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы рассмотрим, руководствуясь [1], класс задач, называемых NP-полными. Для этих задач не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом «P = NP». Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.

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

1. Полиномиальное время

Абстрактные задачи

Как уже упоминалось, понятие полиномиально разрешимой задачи принято считать уточнением идеи «практически разрешимой» задачи. Чем объясняется такое соглашение? Во-первых, используемые на практике полиномиальные алгоритмы обычно действительно работают довольно быстро. Второй аргумент в пользу рассмотрения класса полиномиальных алгоритмов - тот факт, что объем этого класса практически не зависит от выбора конкретной модели вычислений. Например, класс задач, которые могут быть решены за полиномиальное время на последовательной машине с произвольным доступом (RAM), совпадает с классом задач, полиномиально разрешимых на машинах Тьюринга. Класс будет тем же и для модели параллельных вычислений, если, конечно, число процессоров ограничено полиномом от длины входа. В-третьих, класс полиномиально разрешимых задач обладает естественными свойствами замкнутости. Например, композиция двух алгоритмов также работает полиномиальное время. Это объясняется тем, что сумма, произведение и композиция многочленов есть многочлен.

Введем следующую абстрактную модель вычислительной задачи. Будем называть абстрактной задачей - произвольное бинарное отношение Q между элементами двух множеств - множества условий I и множества решений S. Например, в задаче поиска кратчайшего пути между двумя заданными вершинами неориентированного графа G = (V, E) условием (элементом I) является тройка, состоящая из графа и двух вершин, а решением (элементом S) - последовательность вершин, составляющих требуемый путь в графе.

В теории NP-полноты рассматриваются только задачи разрешения - задачи, в которых требуется дать ответ «да» или «нет» на некоторый вопрос. Формально её можно рассматривать как функцию, отображающую множество условий I во множество {0, 1}. Например, с задачей поиска кратчайшего пути в графе связана задача разрешения: «по заданному графу G = (V, E), паре вершин u, v ? V и натуральному числу k определить, существует ли в G путь между вершинами u и v, длина которого не превосходит k».

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

2. Представление данных

Прежде чем подавать на вход алгоритма исходные данные (то есть элемент множества I), надо договориться о том, как они представляются в «понятном для компьютера виде». Будем считать, что исходные данные закодированы последовательностью битов. Формально говоря, представлением элементов некоторого множества S называется отображение e из S во множество битовых строк. Например, целые числа 0, 1, 2, 3, … обычно представляются битовыми строками 0, 1, 10, 11, 100, …

Фиксировав представление данных, мы превращаем абстрактную задачу в строковую, для которой входными данными является битовая строка, представляющая исходные данные абстрактной задачи. Будем говорить, что алгоритм решает строковую задачу за время O (T(n)), если на входных данных (битовой строке) длины n алгоритм работает время O (T(n)). Строковая задача называется полиномиальной, если существует константа k и алгоритм, решающий эту задачу за время O(n^k). Сложностной класс P - множество всех строковых задач разрешения, которые могут быть решены за полиномиальное время, т.е. за время O(n^k), где k не зависит от входа.

Желая определить понятие полиномиальной абстрактной задачи, мы сталкиваемся с тем, что возможны различные представления данных. Для каждого представления e множества I входов абстрактной задачи Q мы получаем свою строковую задачу. Однако на практике (если исключить такие «дорогие» способы представления, как система счисления с основанием 1) естественные способы представления оказываются обычно эквивалентными, поскольку они могут быть полиномиально преобразованы друг в друга. Будем говорить, что функция f: {0,1}* > {0,1}* вычислима за полиномиальное время, если существует полиномиальный алгоритм A, который для любого x ? {0,1}* выдает результат f(x).

Рассмотрим множество I условий произвольной абстрактной задачи разрешения. Два представления e₁ и e₂ этого множества называются полиномиально связанными, если существуют две вычислимые за полиномиальное время функции f₁₂ и f₂₁, для которых f₁₂(e₁(i)) = e₂(i) и f₂₁(e₂(i)) = e₁(i) для всякого i ? I. В этом случае не имеет значения, какое из двух полиномиально связанных представлений выбрать.

3. Формальные языки

Для задач разрешения удобно использовать терминологию теории формальных языков. Алфавитом У называется любой конечный набор различных символов. Языком L над алфавитом У называется произвольное множество строк символов из алфавита У (такие строки называются словами в алфавите У). Например, можно рассмотреть У = {0, 1} и язык L = {10, 11, 101, 111, 1011, …}, состоящий из двоичных записей простых чисел. Будем обозначать символом е пустое слово, не содержащее символов, а символом Ш - пустой язык, не содержащий слов.

Имеется несколько стандартных операций над языками. Операции объединения и пересечения языков определяются как обычные операции объединения и пересечения множеств. Конкатенацией, или соединением, двух языков L₁ и L₂ называется язык L = {x₁x₂ | x₁ ? L₁, x₂ ? L₂} Замыканием языка L называется язык L* = {е} ? L ? L² ? L³ ? …, где L^k - язык, полученный k-кратной конкатенацией L с самим собой. Операция замыкания называется также * - операцией Клини.

Теперь можно сказать, что строковая задача разрешения является языком над алфавитом У. Например, задаче разрешения о существовании в графе пути длины не превосходящей k, соответствует язык PATH = {<G, u, v, k> | G = (V, E) - неориентированный граф, u, v ? V; k ? 0 - целое число, и в графе G существует путь из u в v, длина которого не превосходит k.}

Говорят, что алгоритм A допускает слово x ? {0,1}*, если на входе x алгоритм выдает результат 1; если же A выдает 0, говорят, что он отвергает слово x. Заметим, что алгоритм может не останавливаться на входе x, или дать ответ отличный от 0, 1. В этом случае он и не допускает, и не отвергает слово x. Алгоритм А допускает язык L, если алгоритм допускает те и только те слова, которые принадлежат языку L. Алгоритм А, допускающий некоторый язык L, не обязан отвергать всякое слово x ? L. Если алгоритм A допускает все слова из L, а все остальные отвергает, то говорят, что A распознает язык L. Язык L допускается за полиномиальное время, если имеется алгоритм A, который допускает данный язык, причем всякое слово x ? L допускается алгоритмом за время O(n^k), где n - длина слова x, а k - некоторое не зависящее от x число. Язык L распознается за полиномиальное время, если некоторый алгоритм A распознает данный язык, причем время работы алгоритма на каждом слове длины n не больше O(n^k).

Рассмотренный ранее язык PATH, допускается за полиномиальное время. Нетрудно построить алгоритм, который методом поиска в ширину за полиномиальное время находит кратчайший путь между вершинами u и v в графе G, а затем сравнивает длину найденного пути с данным в условии числом k. Если длина пути не превосходит k, алгоритм выдает 1 и останавливается. В противном случае алгоритм зацикливается, не выдавая никакого ответа. Ясно, что такой алгоритм допускает, но не распознает язык PATH. Однако легко исправить описанный алгоритм таким образом, чтобы слова, не принадлежащие языку, отвергались. Такой алгоритм допускает и распознает язык PATH. Стоит отметить, что некоторые языки (например, для множества всех программ, заканчивающих свою работу) имеют допускающий алгоритм, но не имеют распознающего.

Определение класса задач P мы уже имеем. Дадим определение класса NP. Неформально сложностной класс можно определить как семейство языков, для которых распознающие алгоритмы имеют заданную меру сложности, например заданное время работы. В теории существует множество сложностных классов. Один из них (P) мы уже рассматривали. Есть также не менее важный класс PSPACE - состоящий из задач, решаемых алгоритмами с использованием памяти полиномиального размера. Или класс EXP, состоящий из задач, которые решаются за время O(2^nk). Переформулируем определение класса P: P = {L ? {0,1}* | существует алгоритм A, распознающий L за полиномиальное время.} На самом деле в данной ситуации нет разницы между языками допускаемыми и распознаваемыми за полиномиальное время, о чем свидетельствует следующая теорема.

Теорема

P = {L | L допускается за полиномиальное время}.

Доказательство. Если язык распознается некоторым алгоритмом, то он и допускается тем же алгоритмом. Остается доказать, что если язык L допускается полиномиальным алгоритмом A, то он и распознается некоторым (возможно, другим) полиномиальным алгоритмом A?. Пусть алгоритм A допускает язык L за время O(n^k). Это значит, что существует константа c, для которой A допускает любое слово длины n из L, сделав не более T = cn^k шагов. С другой стороны слова не из L алгоритм не допускает (ни за какое время).

Новый алгоритм A? моделирует работу алгоритма A и считает число шагов этого алгоритма, сравнивая его с известной границей T. Если за время T алгоритм A допускает слово x, алгоритм A? также допускает это слово и выдает 1. Если же A не допускает x за указанное время, то алгоритм A? прекращает моделирование и отвергает слово (выдает 0). Замедление работы за счет моделирования и подсчета шагов не так уж велико и оставляет время работы полиномиальным.

4. Проверка принадлежности языку и класс NP

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

5. Гамильтонов цикл

полиномиальный алгоритм язык гамильтонов

Задача поиска гамильтонова цикла в графе изучается уже более ста лет. Гамильтоновым циклом в неориентированном графе G = (V, E) называется простой цикл, который проходит через все вершины графа. Графы, в которых есть гамильтонов цикл, называют гамильтоновыми. Задача о гамильтоновом цикле состоит в выяснении, имеет ли заданный граф G гамильтонов цикл. Формально говоря, HAM-CYCLE = {<G> | G - гамильтонов граф}. Задача о гамильтоновом цикле является NP-полной, и поэтому можно предполагать, что полиномиального алгоритма для нее вообще не существует. На рисунке ниже приведены примеры двух графов, левый из которых является гамильтоновым, правый же не обладает аналогичным свойством.

6. Проверка принадлежности языку

Определить, является ли граф гамильтоновым, за полиномиальное время, скорее всего, невозможно, однако доказательство существования гамильтонова цикла в графе (состоящее в предъявлении гамильтонова пути) можно проверить за полиномиальное время. Назовем проверяющим алгоритмом алгоритм A с двумя аргументами; первый аргумент - входная строка, а второй - сертификат. A допускает вход x, если существует сертификат y, для которого A (x, y) = 1. Язык, проверяемый алгоритмом A: L = {x ? {0, 1}*: ? y ? {0,1}*, A (x, y) = 1}. Другими словами, алгоритм A проверяет язык L, если для любой строки x ? L найдется сертификат y, с помощью которого A может проверить принадлежность x к языку L, а для x ? L такого сертификата нет. Например, в задаче HAM-CYCLE сертификатом была последовательность вершин, образующая гамильтонов цикл.

7. Сложностной класс NP

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

Более формально. Язык L принадлежит классу NP, если существует такой полиномиальный алгоритм А с двумя аргументами и такой многочлен p(x) с целыми коэффициентами, что L = {x ? {0, 1}*: ?y, для которого |y| ? p (|x|) и A (x, y) = 1}. В этом случае говорят, что A проверяет L за полиномиальное время.

Ранее уже была рассмотрена задача из класса NP - это задача HAM-CYCLE. Кроме того, всякая задача из P принадлежит также NP. Действительно, если есть полиномиальный алгоритм, распознающий язык, то легко построить проверяющий алгоритм для того же языка - проверяющий алгоритм может просто игнорировать свой второй аргумент (сертификат). Таким образом, P ? NP. В данное время неизвестно совпадают ли классы P и NP, но большинство специалистов полагает, что нет. Наиболее серьезная причина полагать, что P ? NP - существование NP полных задач (они будут рассмотрены далее). Кроме проблемы P = NP, остаются открытыми и многие другие вопросы о классе NP. Так, несмотря на огромные усилия исследователей, не известно, замкнут ли класс NP относительно дополнения. Определив сложностной класс co-NP, как множество языков L, для которых ¬L ? NP, можно переформулировать вопрос о замкнутости класса NP относительно дополнения следующим образом: равны ли классы NP и co-NP? Поскольку класс P замкнут относительно перехода к дополнению, P ? NP ? co-NP. В то же время остается неизвестным, верно ли равенство P = NP ? co-NP. Приведенная ниже иллюстрация, отображает четыре возможных ситуации.

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

8. NP-полнота и сводимость

Наиболее убедительным аргументом в пользу того, что классы P и NP различны, является существование так называемых NP-полных задач. Этот класс обладает тем важным свойством, что если какая-нибудь NP-полная задача разрешима за полиномиальное время, то и все задачи из класса NP разрешимы за полиномиальное время, то есть P = NP. В частности, задача HAM-CYCLE является NP-полной. Таким образом, научившись решать ее за полиномиальное время, мы получим полиномиальные алгоритмы для всех задач класса NP. Неформально говоря, NP-полные языки являются самыми «трудными» в классе NP. При этом трудность языков можно сравнивать, сводя один язык к другому. Метод сведения является основным при доказательстве NP-полноты многих задач.

9. Сводимость

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

Теперь дадим формальное определение. Говорят, что язык L₁ сводится за полиномиальное время к языку L₂ (запись: L₁ ?_P L₂), если существует такая функция f: {0,1}* > {0, 1}*, вычислимая за полиномиальное время, что для любого x ? {0, 1}*: x ? L₁ равносильно f(x) ? L₂. Функцию f называют сводящей функцией, а полиномиальный алгоритм F, вычисляющий f, - сводящим алгоритмом. Рисунок, приведенный выше, иллюстрирует данное определение сводимости. Запись L₁ ?_P L₂ можно интерпретировать так: сложность языка L₁ не более чем полиномиально превосходит сложность языка L₂.

Размещено на Allbest.ru