Классы сложности P-SPACE и NP-SPACE

⇐ ПредыдущаяСтр 5 из 8Следующая ⇒

Рассмотрим многоленточную машину Тьюринга, в которой выделена входная и выходная ленты. С входной ленты можно только считать условие задачи, а на выходную - только записать ответ. Кроме того, есть одна или несколько рабочих лент. В качестве меры сложности решения будем теперь брать не время, а память.

Будем говорить, что Z принадлежит классу P-SPACE, если существует детерминированная МТ, которая решает задачу так, что число задействованных для решения ячеек ленты (а это ячейки выходной и рабочих лент) ограничено полиномом от длины входа задачи.

Будем говорить, что Z принадлежит классу NP-SPACE, если существует недетерминированная МТ, которая решает задачу так, что число задействованных для решения ячеек ленты ограничено полиномом от длины входа задачи.

Если алгоритм (например, МТ) работает полиномиальное время, то он, очевидно, использует только полиномиальную память. Поэтому PÍ PSPACE. Но оказывается, что справедливо и более сильное утверждение.

Теорема 9.3. NPÍ PSPACE.

Берется произвольная задача Z из NP и НМТ с алфавитом A, решающая эту задачу за полиномиальное время p(n). Обозначим эту машину через T_Z. Условие полиномиальности влечет за собой полиномиальность длины слова, записанного угадывающей головкой.

Вспомним определение НМТ и смоделируем на его основе уже детерминированную МТ, работу которой представим следующим образом. Входом является условие индивидуальной задачи Z. В МТ входит генератор всех слов в алфавите A, длина которых не превосходит p(n). Таких слов |A|^p(ⁿ⁾. После генерации очередного слова работает T_Z.

Затем слово стирается и на его место записывается очередное слово-отгадка. Такая машина работает уже детерминированно. Время ее работы экспоненциально, но пространство на ленте полиномиально ограничено.

Совершенно аналогично можно доказать и следующее утверждение.

Теорема 9.4. Co-NPÍ PSPACE.

Более того, вспомним задачу " K-е по порядку подмножество". Ее принадлежность к NP невыяснена. Но к классу PSPACE она принадлежит. Построим МТ, которая поочередно просматривает все подмножества множества {1,..., n} и хранит счетчик числа просмотренных подмножеств, вес которых не больше В. В процессе работы каждое следующее проверяемое подмножество записывается на место предварительно стертого предыдущего.

С помощью понятия полиномиальной сводимости можно ввести определение PSPACE-полной задачи. Это такая задача, к которой полиномиально сводятся все задачи из класса PSPACE.

Вообще говоря, между классами P и PSPACE может быть довольно большое различие. Здесь анализ можно проводить в двух направлениях. Рассмотрим их поочередно.

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

Мы уже проводили аналогию между НМТ и обращением к оракулу. А теперь представим себе, что у нас есть множество входных слов I - условий индивидуальных задач некоторой массовой задачи Z. Кроме того, есть два игрока: белый (w) и черный (b), каждый из которых имеет своего карманного оракула. Они делают по очереди свои ходы w₁, … и b₁,.., которые можно представить в виде ответов их оракулов. Число ходов заранее задано. Длина каждого ответа ограничена полиномом от длины входа. Смысл хода белых - получить в результате ответ " да", а черные стремятся к обратному.

Каждую игру из k можно представить в виде последовательности из 2k+1 слова: I, w₁, b₁, …, w_k, b_k. (Последний ход черных может отсутствовать! ) Каждой такой последовательности однозначно соответствует один из двух ответов " да" или " нет". Множества последовательностей с ответом " да" обозначим через W(I, w₁, b₁, …, w_k, b_k). (То есть, на множестве таких последовательностей задан некоторый предикат W(I, w₁, b₁, …, w_k, b_k)). Дополнение этого множества обозначим через B(I, w₁, b₁, …, w_k, b_k).

Можно себе представить эту игру как действие, состоящее из двух этапов. На первом этапе готовится входное слово для МТ. Это слово имеет вид

I#w₁#b₁#…#w_k#b_k.

А на втором этапе МТ отрабатывает на этом слове и останавливается в одном из двух состояний: допускающем слово и отвергающем его.

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

Пусть L_w - множество слов I, на которых выигрывают белые, а через L_b- множество слов I, на которых выигрывают черные.

Поясним сказанное на примере аналогии. Эта аналогия не соответствует описываемой схеме, а только иллюстрирует ее.

Рассмотрим, например, задачу некоторую задачу на графе. Если мы зададим вопрос: «Правда ли, что в графе есть гамильтонов цикл? » - то получим задачу " Гамильтонов цикл". Усложним вопрос: «Правда ли, что в графе есть гамильтонов цикл, но при этом нет клики размером, больше пяти? ». Тогда все графы разделятся на два непересекающихся множества: графы с ответом «да» на поставленный вопрос и графы с ответом «нет». При этом, любой заданный граф принадлежит одному из множеств. Если на нем идет игра, то белые победят в случае ответа «да», а черные – в случае ответа «нет». Эту аналогию можно расширить очевидным образом, например, продолжить вопрос: «Правда ли, что в графе есть гамильтонов цикл, при этом нет клики размером, больше пяти, минимальный тест матрицы смежности графа не меньше семи, а сели его ребрам придать единичные веса, то минимальные обход коммивояжера будет не больше двенадцати? » И т.д.

Теперь можно провести следующие аналогии.

Классу P можно сопоставить множества L_w для игр без ходов (k=0). Тот факт, что P=co-P означает, что классу P можно сопоставить и множества L_b для игр без ходов.

Пусть в игре только белые делают один ход. Тогда получаем аналогию с классом NP. Ход белых - это обращение к оракулу. Если ответом является " да", то оракул предоставит вариант w₁для проверки. Поэтому L_w - это множество слов I, для которых такой вариант существует. Поэтому NP - это совокупность множеств L_w для всех таких игр из одного хода. В рассматриваемой иерархии класс NP будет соответствовать (совпадать) классу S_1.

Пусть в игре только белые делают один ход. Тогда можно получить следующую аналогию с классом co-NP. Ход белых - это обращение к оракулу. Если ответом является " да", то оракул предоставит вариант w₁для проверки. Но такого варианта оракул может не найти, т.е. что бы он не представил, ответом будет " нет". Поэтому L_b - это множество слов I, для которых варианта ответа «да» не существует. Поэтому co-NP - это совокупность множеств L_b для всех таких игр из одного хода. Назовём этот класс P₁. Очевидно, что он является дополнением к классу NP=S₁, состоящему из множеств L_w для таких игр.

Если по одному ходу делают белые и черные, то мы уже выходим за рамки простых аналогий. То есть уже формально появляется новый сложностной класс S₂, состоящий из множеств L_w для таких игр из двух ходов. Можно представить эту игру так. Существует ход (подсказка оракула) белых такой, что при любом ответном ходе белые выигрывают. Другой сложностной класс P₂ состоит из множеств L_b для игр из двух ходов. Здесь содержатся все такие условия индивидуальных задач, то при любом ходе белых черные имеют выигрышный ход. Очевидно, что эти классы взаимно дополнительные, т.е. S₂=co-P₂ и наоборот. Аналогично можно ввести классы S_k и P_k для любых k.

Оказывается, что все эти классы лежат в PSPACE:

Теорема 9.5. Задача Z лежит в классе PSPACE тогда и только тогда, когда существует игра с полиномиальным от длины входа числом ходов и полиномиально вычислимым результатом такая, что L_Z=L_w.

Доказательство. Пусть число ходов ограничено полиномом q(n), а длина каждого записываемого игроками слова ограничена полиномом p(n). Алфавит A конечен |A|=k. Поэтому число всех возможных слов тоже конечно.

Сначала докажем, что игра с полиномиальным от длины входа числом ходов и полиномиально вычислимым результатом лежит в классе PSPACE.

Построим следующее корневое дерево T. Его корнем будет I. Затем последовательно идут ярусы, соответствующие ходам первого и второго игрока. На каждом ярусе расположены вершины, соответствующие всем возможным ходам игрока.

Каждой вершине можно приписать метку w или b в зависимости от того, кто в данной вершине имеет выигрышную стратегию. По эти меткам можно определить. Кто имеет выигрышную стратегию на всем дереве, т. е. на входе I.

Метки расставляются следующим способом. Каждому листу дерева, а это узлы яруса y_q₍_n)(или x_q₍_n), если нет последнего хода черных) однозначно сопоставлено значение предиката. Если предикат принимает истинное значение, то пометкой будет w, в противном случае - b. Затем поочередно рассматриваем узлы яруса x_q₍_n)и вершине приписываем пометку w, если все ее дети имеют пометку w. В противном случае ставим пометку b. По этому правилу помечаем все ярусы, соответствующие ходам первого игрока. Вершины ярусов, соответствующие ходам второго игрока, помечаем следующим образом. Если среди детей есть хотя бы одна, помеченная как w, то пометкой будет w. В противном случае - b. По этим пометкам однозначно восстанавливается исход игры на входе I. Таким образом, для решения задачи Z нужно построить МТ, моделирующую вышеприведенный процесс расстановки пометок и вычисления значений предиката на листьях дерева. Число вершин в дереве полиномиально, полиномиально и время одной проверки значения предиката. Поэтому данная МТ требует O(p(n)q(n)) ячеек памяти. В одну сторону теорема доказана.

Пусть теперь есть некоторая задача Z в классе PSPACE. Покажем теперь, что существует игра с полиномиальным от длины входа числом ходов и полиномиально вычислимым результатом такая, что L_Z=L_w.

Итак, у нас есть МТ, распознающая на полиномиальной памяти вхождение слова в язык L_Z. Пусть размер памяти p(x). Построим допускающую таблицу такой машины. Как бы не заполняли такую таблицу в конечном алфавите A, |A|=h, с множеством состоянийS, |S|=s, разных таблиц будет не более (h+s)^p(^x)p(x). Поэтому можно считать, что время работы МТ ограничено экспонентой 2^q(^x), где q(x) — некоторый полином, а допускающая таблица имеет q(x) столбцов и 2^q(^x)строк.

	…	q(x)


…

2^q(x)

Игра состоит в следующем. Задан вход I. Белые утверждают, что на этом слове МТ дает ответ " да". Черные хотят проверить. Первым ходом белые записывают состояние МТ после 2^q(^x)тактов работы. Черные своим ходом выбирают один из двух промежутков: от начала до 2^q(^x)–1-го такта или от 2^q(^x)–1-го такта до конца. В середине выбранного черными промежутка белые вновь декларируют состояние МТ, черные выбирают одну из половинок этого промежутка. Игра заканчивается за O(q(n)) шагов в тот момент. Когда длина промежутка стала равной единице, т.е. он содержит два последовательных состояния. Если между этими состояниями существует корректный переход в данной МТ, то выиграли белые, в противном случае выигрывают черные.

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

Теорема доказана.

Обозначим через TIME(f(n)) класс задач (языков), для которых существует МТ, время работы которой ограничено f(n). В частности, если f(n) экспонента, то соответствующий класс обозначается через EXPTIME.

Заметим, что при доказательстве предыдущей теоремы мы показали, что

PSPACEÍ EXPTIME.

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

⇐ Предыдущая 1 2 3 456 7 8 Следующая ⇒