NP-полнота. 
Конструирование приближенных алгоритмов

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

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

Будем называть задачу полиномиальной, если существует константа k и некоторый алгоритм, который решает эту задачу за время O (nk), т. е. полиномиальное время. Рассмотрим определения классов P и NP:

Сложностной класс P — это множество всех строковых задач разрешения. Решение для них может быть найдено за полиномиальное время, т. е. за время O (nk), при этом k не зависит от входа.

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

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

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

Приведем понятие сводимости. Говорят, что язык L1 сводится за полиномиальное время к языку L2 (L1 ?P L2), если существует вычислимая за полиномиальное время функция f: {0,1}* > {0, 1}*, такая что для любого x? {0, 1}*: x? L1 равносильно f (x)? L2.

При этом функцию f называют сводящей, а алгоритм F, вычисляющий f — сводящим. Запись L1? P L2 можно интерпретировать следующим образом: сложность языка L1 не более чем полиномиально превосходит сложность языка L2.

Сводимость позволяет формализовать сравнение языков по их трудности. В этом смысле наиболее трудными являются NP-полные задачи. Язык L? {0, 1}* называется NP-полным, если L? NP и L? ?P L для любого L?? NP. Обозначим данный класс языков как NPC (NP-complete). Ниже представлена диаграмма Венна для случаев P = NP и P ≠ NP.

Рассмотрим несколько NP-полных задач:

Простой цикл в неориентированном графе G = (V, E), проходящий через все его вершины называется гамильтоновым.

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

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

Задача о клике была сформулирована в 1972 году Ричардом Карпом. Это NP-полная задача в области теории графов.

Граф с кликой размера 3.

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

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

В дальнейшем в работе будем рассматривать задачу маршрутизации транспорта (VRP).