ЛЕКЦИЯ 13. ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О СТРУКТУРЕ КЛАССА NP.

Мы уже знаем, что PÍ NP. Как показал Ладнер, если P≠ NP , то имеется еще целое множество языков в NP, для которых нет полиномиального алгоритма, но сами эти языки не являются полными в классе NP.

В качестве кандидатов на такие языки выступают следующие две известные задачи.

ЗАДАЧА ИЗОМОРФИЗМ ГРАФОВ. Пусть даны два графа. Спрашивается, можно ли так пронумеровать их вершины, что их матрицы инциденций полностью совпадут (читай – один граф можно целиком наложить на другой и наоборот).

ПРОБЛЕМА ПРОВЕРКИ ПРОСТОТЫ ЧИСЛА.Эта проблема имеет важное значение для криптографии (шифрования). Известные алгоритмы проверки чисел на простоту являются переборными.

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

co-L Î NP

если произвольное слово (задача) y принадлежит L, то у не принадлежит co-L. Наоборот, если y принадлежит co-L, то у не принадлежит L.

Определение. Класс co-NP - это класс всех языков, дополнительных к языкам из NP.

Очевидным образом co-NP Í NP. Обратное соотношение является открытой математической проблемой.

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

Примером NP-трудной задачи является задача построения минимальной КНФ (конъюнктивной нормальной формы). Применительно к задаче ВЫП это равносильно построить эквивалентную ей ВЫП минимальных размеров.

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

Определение. Класс PSPACE – это класс задач распознавания типа ДА-НЕТ, требующих полиномиальных размеров памяти для решающих их детерминированных алгоритмов.

Определение.Класс NPSPACE – это класс задач распознавания типа ДА-НЕТ, требующих полиномиальных размеров памяти для решающих их недетерминированных машин Тьюринга.

Имеет место следующее важное соотношение:

PÍNPÍPSPACE=NPSPACE

Результат PSPACE=NPSPACE известен как теорема Савича. Эта теорема доказывается, исходя из того, что для каждой недетерминированной машины Тьюринга имеется эквивалентная ей детерминированная машина Тьюринга. На этом важном вопросе мы остановимся более подробно.

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

Qi aj ® Qk al R(L) (1)

Qi aj ® Qm an R(L) (2)

В левой части записаны одинаковые состояния и символы. Теперь наша моделирующая машина перепишет состояние ленты в этот момент в свободном месте, т.е. создаст копию ленты на ленте! На оригинале наша машина будет применять правило (1), а на копии – правило (2), т.е. как бы работать уже с двумя машинами по очереди. Если встретится новое альтернативное правило, то создается третья копия на ленте и процесс разветвляется уже на три потока и т д. Таким образом, детерминированная машина работает по нескольким ветвям одновременно до тех пор, пока не получит результат по какой-нибудь одной из ветвей.