Подход к решению задач недетерминированной полиномиальной сложности.

Класс Р (полиномиальные задачи):

Akxk + ak-1xk-1 +…+a0x0

Задача называется полиномиальной, т. е. относится к классу Р, если существует константа k и алгоритм, решающий эту задачу за время O(nk), где п есть длина входа алгоритма в битах . Отметим, что класс задач Р определяется через существование полиномиального по времени алгоритма ее решения, при этом неявно предполагается худший случай по времени для всех различных входов длины n. Задачи класса Р - это задачи, решаемые за реальное время. Отметим следующие преимущества задач из этого класса:

- для большинства реальных задач из класса Р константа k меньше 6;

- класс Р инвариантен по модели вычислений (для широкого класса моделей);

- класс Р обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).

Таким образом, задачи класса Р есть уточнение определения «практически разрешимой» задачи для входов больших размерностей.

Класс NP (полиномиально проверяемые задачи):

Понятие NP-полноты было введено независимо Куком (Stephen Cook, 1971) и Левиным (1973) и основывается на понятии сводимости одной задачи к другой. Сводимость задач может быть представлена следующим образом: если мы имеем задачу 1 и решающий эту задачу алгоритм, выдающий правильный ответ для всех конкретных проблем, а для задачи 2 алгоритм решения неизвестен, то если мы можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2 с помощью алгоритма решения задачи 1. Таким образом, если задача 1 задана множеством конкретных проблем DA1,а задача 2 - множеством DA2, и существует функция fs (алгоритм), сводящая конкретную постановку dA2 задачи 2 к конкретной постановке dA1 задачи 1, т.е. fs(dA2 € DA2) = dA1 e DA1 , то задача 2 сводима к задаче 1. Если при этом временная сложность алгоритма fs есть 0(nk), т.е. алгоритм сведения принадлежит классу Р, то говорят, что задача 2 полиномиально сводится к задаче 1. В теории сложности вычислений принято говорить, что задача задается некоторым языком, тогда если задача 1 задана языком L1, а задача 2 - языком L2, то полиномиальная сводимость языков, задающих задачи, обозначается следующим образом: L2 <=p L1

Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: во-первых, задача должна принадлежать классу NP, и, во-вторых, к ней полиномиально должны сводиться все задачи из класса NP. Для класса NPC доказана следующая теорема:

Если существует задача, принадлежащая классу NPC, для которой существует полиномиальный алгоритм решения, то класс Р совпадает с классом NP, т.е. P = NP.

Схема доказательства состоит в сведении с полиномиальной трудоемкостью любой задачи из класса NP к данной задаче из класса NPC и решении этой задачи за полиномиальное время (по условию теоремы). В настоящее время доказано существование сотен NP-полных задач, но ни для одной из них пока не удалось найти полиномиального алгоритма решения. Отметим, что для многих из них предложены приближенные полиномиальные алгоритмы. Сегодня ученые предполагают следующее соотношение классов - Р <> NP, то есть NP \ Р <> 0, и ни одна задача из класса NPC не может быть решена, по крайней мере, сегодня, с полиномиальной сложностью.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.