19. Обчислювальна складність задач. Класи задач p та np.

Сложности задачи характеризуют сложностью наилучшего алгоритма, решающего задачу с самым трудным значением входа.

Сводимость задач

Пусть имеем задачи Z₁ и Z₂ . Пусть имеем также алгоритм S, позволяющий получить решение задачи Z₁ из решения задачи Z₂. Таким образом, получить решение задачи Z₁ мы можем, решив задачу Z₂ (с соответствующими входными данными) и преобразовав это решение в искомое решение задачи Z₁ с помощью алгоритма S.

Говорят, что задача Z₁ полиномиально сводится к задаче Z₂, если существует алгоритм S полиномиальной сложности, позволяющий получить решение задачи Z₁ из решения соответствующей задачи Z₂.

Теорема 1

Если задача Z₁ полиномиально сводится к задаче Z₂, тогда:

 если задача Z₂ имеет полиномиальную сложность, то и задача Z₁ также имеет полиномиальную сложность;

 если задача Z₂ имеет сложность выше полиномиальной, то сложность задачи Z₁ соответствует сложности задачи Z₂.

Отметим, что если задача Z₂ имеет полиномиальную сложность и полиномиальная сводимость задачи Z₁ к задаче Z₂ доказана, то тем самым доказана полиномиальная сложность задачи Z₁.

Различают 3 основных класса сложности задач:

1) задачи, для которых известны алгоритмы полиномиальной сложности;

2) задачи, для которых не известны алгоритмы полиномиальной сложности, но для которых и не доказано несуществование таких алгоритмов;

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

Задачи, которые не принадлежат первому классу называют труднорешаемыми.

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

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

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

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

Очевидно, что P  NP .

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

Задача называется NP-трудной , если любая задача из NP полиномиально сводится к ней.

Задача называется NP-полной , если она является NP-трудной и в то же время принадлежит к классу NP.

Таким образом, имеют место следующие соотношения:

{NP-полные}  {NP-трудные}

сложность(NP-полная)  сложность(NP-трудная) .

Примеры задач разной сложности

Полиномиальная сложность:

- задачи о кратчайших путях и маршрутах на графах;

- задача о максимальном потоке транспортной сети;

- задачи о паросочетаниях, о назначениях (двудольные графы).

Экспоненциальная сложность:

- задача установления изоморфности графов.

NP-трудные задачи:

- поиск максимальной клики и определение плотности графа;

- определить, является ли заданный граф гамильтоновым;

- задача коммивояжера;

- задача о набольшем общем подграфе;

- задача о взломе шифра.

Задача определения изоморфности графов

О задаче определения изоморфности двух графов известно, что она принадлежит NP , но не известно, принадлежит ли она классу P и является ли она NP-полной [3-460, 4-78]. В то же время более сложная задача: определить, изоморфен ли граф G₁ какому либо подграфу графа G₂, является NP-полной [4-74]. Задача о выделении максимального множества независимых вершин является NP-полной даже для класса планарных графов [4-74].