10.3. ЯЗЫКИ И ЗАДАЧИ

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

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

1. Целые числа будем представлять в десятичной системе счисления.

2. Узлы графа будем представлять целыми числами закодированными как десятичные числа в соответствии с соглашением 1. Ребро будем представлять цепочкой где десятичные представления пары узлов, определяющей это ребро.

3. Булевы выражения (формулы) с пропозициональными переменными будем представлять цепочками, в которых представляет "и", + представляет "или", представляет "не", а целые числа представляют

пропозициональные переменные. Знак когда можно, опускается. Если нужно, будем ставить скобки.

Теперь мы можем сказать, что задача принадлежит 5 или если ее стандартный код принадлежит или соответственно.

Пример 10.3. Рассмотрим задачу о клике для неориентированных графов, -кликой в графе называют -узельный полный подграф (каждая пара различных узлов в этом подграфе соединена ребром) графа Задача о клике формулируется так: содержит ли данный граф -клику, где данное целое число?

Пример задачи о клике для графа на рис. 10.5 при можно закодировать цепочкой

Первое число представляет значение За ним идут пары узлов, соединенных ребрами, причем узел представлен числом Таким образом, ребра в порядке перечисления выглядят так:

Язык представляющий задачу о клике, образуют такие цепочки вида

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

Рис. 10.5. Неориентированный граф.

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

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

Пример 10.4. Булеву формулу можно представить, цепочкой где число представляет переменную Рассмотрим язык образованный всеми цепочками, представляющими выполнимые булевы формулы (т. е. формулы, принимающие значение 1 на некотором наборе 0-1-значений переменных). Мы утверждаем, что принадлежит Недетерминированный алгоритм, распознающий начинает с того, что "угадывает" выполняющий набор 0-1-значений пропозициональных переменных во входной цепочке, если такой набор существует. Затем угаданное значение (0 или 1) каждой переменной подставляется вместо всех вхождений этой переменной во входную цепочку. Чтобы закрыть дыры, образующиеся в цепочке в результате подстановки одного символа или 1 вместо десятичного представления пропозициональной переменной, потребуются некоторые сдвиги цепочки. Далее вычисляется значение полученного выражения, чтобы проверить его совпадение с 1.

Это вычисление осуществляется за время, пропорциональное длине выражения, многими алгоритмами синтаксического анализа (см. Ахо, Ульман [1972]). Но даже и без них не трудно вычислить значение булевой формулы за шагов. Следовательно, некоторая недетерминированная машина Тьюринга допускает выполнимые булевы формулы с полиномиальной временной сложностью, и потому задача распознавания выполнимости булевых формул принадлежит Снова отметим, что недетерминизм пригодился, чтобы "параллелизовать" задачу, поскольку "угадывание" правильного решения в действительности означает параллельную проверку всех возможных решений. Как будет показано позже, эта задача также NP-полна.

Часто нас интересуют задачи оптимизации, например нахождение наибольшей клики в графе. Многие такие задачи можно преобразовать за полиномиальное время в задачи распознавания языка. Например, наибольшую клику в графе можно найти так:

Пусть длина представления графа Для каждого от 1 до выясняем, содержит ли граф клику размера Установив таким образом размер наибольшей клики, удаляем по одному узлу до тех пор, пока удаление очередного узла не разрушит все оставшиеся клики размера Затем рассмотрим подграф состоящий из всех узлов графа смежных с Рекурсивно вызывая этот процесс, находим клику С размера Наибольшей кликой для будет

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

С помощью двоичного поиска (разд. 4.3) часто можно решить задачу оптимизации вида "найти такое наибольшее что истинно", где некоторое условие, а число допустимых оценивается экспонентой от длины описания задачи. Если из истинности следует истинность для изменяется от до где с — некоторая постоянная, то наибольшее для которого истинно можно найти двоичным поиском, проведя с проверок условия Читателю снова предлагаем убедиться в том, что оптимальное значение можно найти за время, полиномиально зависящее от и от наибольшего времени проверки

Разработку техники подобного рода предоставляем изобретательности читателя и в дальнейшем будем заниматься только задачами, требующими ответа "да" или "нет".