Упражнения с решениями - Урок 9 - PSPACE: класс задач за пределами NP

Упражнение с решением 1

Самоизбегающие блуждания изучаются в области статистической физики; их можно определить следующим образом. Пусть L — множество всех точек R² с целочисленными координатами (своего рода “сетка” на плоскости). Самоизбегающее блуждание Wдлины n представляет собой последовательность точек (p₁, p₂, ..., p_n) из L, для которых

(i) p₁ = (0,0) (перемещение начинается от начала координат);

(ii) в последовательности нет двух одинаковых точек (“маршрут” не повторяется);

(iii) для всех i = 1, 2, ..., n - 1 точки p_i и p_i+1 находятся на расстоянии 1 друг от друга (перемещение происходит между соседними точками в L).

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

В этой области существует знаменитая нерешенная задача: для натурального числа n ≥ 1 количество разных самоизбегающих блужданий длины n обозначается A(n). Обратите внимание: блуждания рассматриваются как последовательности точек, а не как множества; даже если два блуждания проходят через одно множество точек, но в разном порядке, они считаются разными. (Формально блуждания (p₁, p₂, ..., p_n) и (q₁, q₂, ..., q_n) считаются разными, если для некоторого i (1 ≤ i ≤ n) p_i ≠ q_i.) Пример изображен на рис. 9.3. В полимерных моделях, основанных на самоизбегающих блужданиях, величина A(n) напрямую связана с энтропией цепочечной молекулы и поэтому встречается в теориях, относящихся к частоте некоторых метаболических реакций и реакций органического синтеза.

Несмотря на важность величины A(n), простая формула для нее неизвестна. Алгоритм для вычисления A(n) с временем, полиномиальным по n, пока не найден.

Рис. 9.3. Три разных самоизбегающих блуждания длины 4. Обратите внимание: блуждания (a) и (b) состоят из одинаковых множеств точек, но считаются разными, потому что они обходятся в разном порядке

(a) Покажите, что A(n) ≥ 2^n-1 для натуральных чисел n ≥ 1.

(b) Предложите алгоритм, который получает число n и выводит A(n) как число в двоичной системе счисления с затратами пространства (то есть памяти), полиномиальными по n. (Таким образом, время выполнения алгоритма может быть экспоненциальным при условии полиномиальных затрат пространства. Также обратите внимание на то, что под полиномиальностью имеется в виду “полиномиальность по n”, а не “полиномиальность по log n”. В самом деле, из (а) следует, что для записи значения А(n) потребуется не менее n - 1 битов, поэтому очевидно, что n - 1 является нижней границей для пространства, необходимого для получения правильного ответа.)

Решение

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

Итак, сделаем шаг назад; полиномиальное пространство — очень свободная граница, и мы можем сделать шаг в сторону “грубой силы”. Допустим, вместо того, чтобы пытаться перебрать все самоизбегающие блуждания длины n, мы просто переберем все блуждания длины n, а затем проверим, какие из них окажутся само- избегающими. Преимущество такого решения в том, что пространство всех блужданий описывается намного проще, чем пространство самоизбегающих блужданий.

В самом деле, любое блуждание (р₁, р₂, ..., p_n) для множества L точек сетки на плоскости может быть описано последовательностью выбираемых направлений. Каждый шаг от р_i к р_i+1 может рассматриваться как перемещение в одном из четырех направлений: север, юг, восток или запад. Следовательно, любое блуждание длины n отображается на строку длины n - 1 в алфавите {N, S, E, W}. (Три блуждания на рис. 9.3 соответствуют строкам ENW, NES и EEN). Каждая такая строка соответствует блужданию длины n, но не все такие строки соответствуют самоизбегающим блужданиям: например, NESW возвращается к точке (0, 0).

Этот способ кодирования блужданий для части (b) вопроса можно использовать следующим образом. Используя счетчик по модулю 4, мы перебираем все строки длины n - 1 по алфавиту {N, S, E, W}, рассматривая этот алфавит в эквивалентном виде {0, 1, 2, 3}. Для каждой такой строки мы строим соответствующее блуждание и проверяем с полиномиальными затратами пространства, является ли оно самоизбегающим. Наконец, мы увеличиваем второй счетчик A (инициализируемый 0), если текущее блуждание является самоизбегающим. В конце алгоритма в A хранится значение А(n).

Теперь мы можем ограничить пространство, используемое алгоритмом, следующим образом. Первый счетчик, используемый для перебора строк, состоит из n - 1 позиции, каждая из которых занимает два бита (для четырех возможных значений). Второй счетчик, содержащий А, может увеличиваться не более 4^п-1 раз, поэтому для него понадобится не более 2n битов. Наконец, полиномиальное пространство используется для проверки того, является ли каждое сгенерированное блуждение самоизбегающим; но одно и то же пространство может использоваться для всех блужданий, поэтому необходимое пространство также является полиномиальным.

Описанная схема кодирования также помогает ответить на часть (а). Заметим, что все блуждания, которые могут быть закодированы с использованием только букв {N, E}, являются самоизбегающими, так как перемещение на плоскости осуществляется только вверх и вправо. Для этих двух букв существуют 2^n-1 строки длины n - 1, поэтому существуют не менее 2^n-1самоизбегающих блужданий; другими словами, A(n) ≥ 2^n-1.

(Ранее было показано, что наш метод кодирования также предоставляет верхнюю границу, из которой немедленно следует, что A(n) ≤ 4^n-1.)

Упражнения

1. Рассмотрим частный случай задачи 3-SAT с кванторами, в котором булева формула не содержит инвертированных переменных. А именно, пусть Ф(х₁, ..., x_n) — булева формула вида

C₁ Λ C₂ Λ ... Λ C_k,

где каждое условие C_i является дизъюнкцией трех литералов. Монотонность Ф означает, что каждый литерал в каждом условии состоит из неинвертированной переменной, то есть что каждый литерал равен х_i для некоторого i, а не

Монотонная задача QSAT определяется как задача принятия решения

в которой формула Ф является монотонной.

Сделайте одно из двух: (а) докажите, что монотонная задача QSAT является PSPACE-полной; или (b) предложите алгоритм для решения произвольных экземпляров монотонной задачи QSAT за время, полиномиальное по n. (Обратите внимание: в (b) целью является полиномиальное время, а не полиномиальное пространство.)

2. Рассмотрим следующую игру. Имеется множество географических названий — например, названий столиц. Первый игрок называет столицу с страны, в которой находится компания; второй игрок должен выбрать город с', начинающийся с буквы, которой заканчивается c. Далее игроки попеременно выбирают города, начинающиеся с последней буквы предыдущего города. Проигрывает тот, кто не может назвать город, еще не встречавшийся ранее в игре. Например, в начале игры, проходящей в Венгрии, первый игрок говорит “Будапешт”; далее следует продолжение (например): “Токио, Оттава, Анкара, Амстердам, Москва.”

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

Чтобы выделить стратегический аспект, определим абстрактную версию игры, которая будет называться географической игрой на графе. Имеется направленный граф G = (V, E) с начальным узлом s ∈ V. Игроки поочередно делают ходы, начиная с s; каждый игрок должен по возможности перейти по ребру от текущего узла к узлу, который ранее не посещался. Проигрывает тот игрок, который первым не сможет перейти к узлу, ранее посещавшемуся в игре (по прямой аналогии с игрой, только узлы соответствуют словам). Другими словами, игрок проигрывает, если в игре в данный момент текущим является узел v и для всех ребер вида (v, w) узел w уже посещался.

Докажите, что задача принятия решения о том, может ли первый игрок обеспечить себе победу в географической игре на графе, является PSPACE-полной.

3. Предложите алгоритм с полиномиальным временем для принятия решения о том, может ли первый игрок обеспечить себе победу в географической игре на графе в особом случае, когда граф G не имеет направленных циклов (иначе говоря, когда G является направленным ациклическим графом).

Примечания и дополнительная литература

PSPACE — всего лишь один класс неразрешимых задач за пределами NP; изучением этой области занимается теория сложности. По теме теории сложности написан ряд книг, таких как книги Пападимитриу (Papadimitriou, 1995) и Сэвиджа (Savage, 1998).

PSPACE-полноту задачи QSAT доказали Стокмейер и Мейер (Stockmeyer, Meyer, 1973).

Некоторые базовые результаты PSPACE-полноты для игр с двумя участниками приведены у Шефера (Schaefer, 1978), а также у Стокмейера и Чандры (Stockmeyer, Chandra, 1979). Задача конкурентного размещения, рассматриваемая здесь, является адаптированным примером класса задач, изучаемых более общей областью размещения объектов; например, обзорную информацию по этой теме можно найти в книге под редакцией Дрезнера (Drezner, 1995).

Игры для двух игроков постоянно порождали сложные вопросы для ученых в области математики и искусственного интеллекта. Берлекамп, Конуэй и Гай (Berlekamp, Conway, Guy, 1982) и Новаковски (Nowakowski, 1998) обсуждают некоторые математические вопросы в этой области. Разработка шахматной программы уровня чемпиона мира в течение 50 лет считалась основной задачей прикладного программирования в области компьютерных интеллектуальных игр. Известно, что Алан Тьюринг работал над алгоритмами для игры в шахматы, как и многие ведущие специалисты в области искусственного интеллекта тех лет. Ньюборн (Newborn, 1996) рассказывает об истории работы над задачей вплоть до момента за год до того, как компьютеру IBM DeepBlue наконец-то удалось победить чемпиона мира.

Построение плана относится к числу фундаментальных задач в области искусственного интеллекта; она занимает видное место в работе Рассела и Норвига (Russell, Norvig, 2002), а также является темой книги Галлаба, Нау и Траверсо (Ghallab, Nau, Traverso, 2004). Обоснование возможности решения задачи построения плана с полиномиальным пространством приводится в работе Савича (Savitch, 1970), посвященной вопросам теории сложности, а не задаче построения плана как таковой.

Примечания к упражнениям

Упражнение 1 основано на задаче, о которой мы узнали от Мэверика Ву и Райана Уильямса; упражнение 2 основано на результате Томаса Шефера.