10.2. КЛАССЫ ...

Введем два важных класса языков.

Определение. Определим как множество всех языков, допускаемых ДМТ с полиномиальной временной сложностью,

существуют такие ДМТ M и полином что временная сложность машины равна

Определим как множество всех языков, допускаемых НМТ с полиномиальной временной сложностью. Для краткости мы будем часто писать вместо и -ТШЕ соответственно.

Прежде всего заметим, что, хотя классы определены в терминах машин Тьюринга, можно было бы использовать любую из многих других моделей вычислений. Интуитивно можно представлять себе как класс языков, распознаваемых за полиномиальное время. Например, мы показали, что если язык допускается машиной Тьюринга с временной сложностью то временная сложность его распознавания на РАМ или РАСП при логарифмическом весовом критерии будет лежать между где и некоторые положительные постоянные. Таким образом, язык допускается машиной Тьюринга с полиномиальной временной сложностью тогда и только тогда, когда существует алгоритм его распознавания, реализуемый на РАМ или РАСП с полиномиальной сложностью при логарифмическом весовом критерии.

Можно также определить недетерминированную РАМ или РАСП, добавив к системе команд команду означающую, что недетерминированны выбор и последующее выполнение одного из операторов Таким образом, класс можно также определить с помощью недетерминированных РАМ или РАСП с полиномиально ограниченной временной сложностью при логарифмическом весовом критерии.

Следовательно, можно представить себе недетерминированную вычислительную машину вроде РАМ или РАСП, способную выполнить много различных возможных последовательностей шагов, начинающихся с данного МО. Оказывается, такое устройство может распознать за полиномиальное время многие языки, по-видимому нераспознаваемые за полиномиальное время детерминированными алгоритмами. Разумеется, любая попытка прямого моделирования недетерминированного устройства детерминированным устройством выполняющим все возможные последовательности шагов, занимает гораздо больше времени, чем любая единичная реализация последовательности шагов устройства поскольку должно прослеживать работу огромного количества копий На основе результатов предыдущего раздела мы можем утверждать лишь, что если язык принадлежит он допускается некоторой ДМТ с временной сложностью где постоянная и полином, зависящие от

С другой стороны, еще никому не удалось доказать, что существует язык из не принадлежащий Таким образом, неизвестно, является ли собственным подклассом класса Однако можно

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

Определение. Язык из называется полным для недетерминированного полиномиального времени (или NP-полньш), если выполнено следующее условие: по данному детерминированному алгоритму распознавания с временной сложностью и любому языку из можно эффективно найти детерминированный алгоритм, распознающий за время где некоторый полином, зависящий от Говорят, что сводится к -полноту языка можно доказать, показав, что принадлежит и каждый язык можно "полиномиально трансформировать" в

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

Если язык трансформируем в распознается некоторым детерминированным алгоритмом А с временной сложностью то можно выяснить принадлежность цепочки языку преобразовав с помощью машины и затем применив А для выяснения принадлежности языку Если время работы машины ограничено полиномом то Таким образом, существует алгоритм, выясняющий принадлежность языку за время Если бы функция была полиномом (т. е. язык принадлежал бы , то этот алгоритм, распознающий работал бы полиномиально ограниченное время, и язык также принадлежал бы

Некоторые авторы, действительно, определяют язык как NP-полный, если он принадлежит и каждый язык из полиномиально трансформируем в Это определение представляется более узким, чем предыдущее, хотя не известно, приводят ли указанные два определения NP-полных языков к разным классам. Определение, основанное на сводимости, означает, что если детерминированная машина Тьюринга, распознающая NP-полный язык за время то всякий язык из можно распознать за время где некоторый полином, с помощью детерминированной машины Тьюринга, которая обращается к М0 как к подпрограмме нуль или более раз. Определение, основанное на

трансфермируемости, означает, что к М0 можно обратиться лишь один раз и затем использовать результат ее работы заранее фиксированным образом. Хотя мы примем более широкое определение, все наши доказательства NP-полноты проходят и для узкого определения.

Какое бы из этих определений ни взять, ясно, что если некоторый детерминированный алгоритм распознает за полиномиальное время, то все языки из можно распознать за полиномиальное время. Таким образом, либо все NP-полные языки принадлежат 5, либо ни один из них не принадлежит Первое верно тогда и только тогда, когда . К сожалению, в настоящее время мы можем лишь выдвинуть гипотезу о том, что 5 — собственный подкласс класса