Классы NP и co-NP

Для любой Z задачи из NP можно сформулировать дополнительную задачу (язык) Z'. Если язык L_Z образуют все слова, являющиеся условием индивидуальных задач с ответом "да", то язык L_Z' образуют все слова, являющиеся условием индивидуальных задач с ответом "нет". Совокупность таких "дополнительных" задач и составляет класс co-NP. Аналогично для класса P может быть определен класс co-P.

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

Предполагается, что последние можно отсеять с помощью каких-то вспомогательных "простых" процедур, например, синтаксических проверок и т.п.

Для любой задачи из класса P дополнение можно получить заменой заключительного состояния (q_no заменяем на q_yes и наоборот). Так как нет никакой угадывающей головки, то на любом корректно заданном условии задачи МТ остановится. Таким образом, мы автоматически получаем из МТ, решающей задачу Z, МТ для решения Z'. Поэтому классы P и co-P совпадают.

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

Рассмотрим следующий алгоритм. Берем пустое множество W.

1 шаг. На первом шаге включаем в него некоторую вершину v. Она считается помеченной, но не просмотренной. Переходим ко второму шагу.

2 шаг. Включаем в W всех соседей всех непросмотренных вершин. После этого только вновь включенные вершины считаются помеченными, но непросмотренными. Переходим к шагу 3.

3 шаг. Если W=V, то ответ "да". Если W¹V и непросмотренных вершин нет, то ответ "нет". В остальных случаях переходим к шагу 2.

Ясно, что шагов не более n. И на каждом шаге не более m проверок. Очевидно, что данный алгоритм решает как задачу с вопросом, связен ли G, так и задачу с вопросом, является ли G несвязным.

Для NP и co-NP ситуация иная. Например, обратная к задаче "гамильтонов цикл" задача состоит в ответе на вопрос: "Правда ли, что в данном графе нет гамильтонова цикла?" Как здесь может выглядеть подсказка? На сегодняшний день единственной возможной подсказкой представляется выписывание всех возможных гамильтоновых циклов и проверка их отсутствия в данном графе.

n!

……

Условие

Отгадки (граф G)

(все возможные циклы)

Но такой список циклов имеет экспоненциальную длину.

Поэтому вопрос о соотношении NP и co-NP является открытым.

Теорема 9.2. Если существует NP-полная задача Z такая, что ее дополнение лежит в NP, то

NP=co-NP.

Доказательство строится конструктивно с помощью композиции машин Тьюринга.

Пусть дополнение Z' некоторой NP-полной задачи Z лежит в NP. Покажем, что тогда дополнение W' любой задачи W лежит в NP. По определению полиномиальной сводимости функция f, осуществляющая эту сводимость, например, задачи W к задаче Z одновременно осуществляет полиномиальную сводимость задачи W' к задаче Z'. Функция f (одна МТ) вычисляется за полиномиальное время, проверка принадлежности Z' к NP (другая МТ, уже недетерминированная) тоже вычисляется за полиномиальное время. Поэтому проверка принадлежности W' к NP осуществляется путем последовательной комбинации этих двух машин, т.е. может быть проведена за полиномиальное время на недетерминированной МТ.

Дата добавления: 2015-07-11