Альтернирование: существование хода и ответ на любой ход

Если читаешь дерево AND/OR как игру - переходи к «Теперь сам».

Как думаешь: можно ли заменить стратегию одним удачным ходом?

Ты выбираешь настройку сервиса, затем противник выбирает сбой, затем ты выбираешь способ восстановления. Условие «существует настройка, для любого сбоя существует восстановление» допускает разные восстановления после разных сбоев. Требование «существует настройка и один способ восстановления, подходящий для любого сбоя» сильнее.

В задаче о формуле с кванторами уже встретились эти две роли. Здесь тот же порядок разрешается прямо в модели вычисления. Цена измеряется длиной одной партии, а успешность - всем деревом возможных ответов. Полиномиальная длина партии не делает дерево полиномиальным.

На что это похоже

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

Механизм: два вида конфигураций

Конфигурация машины содержит состояние, рабочую ленту и положения головок. В экзистенциальной конфигурации, помеченной ∃, достаточно одного принимающего потомка. В универсальной, помеченной ∀, должны принять все потомки. Лист сразу имеет ответ «принять» или «отвергнуть». При ограниченном времени все ветви заканчиваются, и значение дерева определяется снизу вверх.

Обычная недетерминированная машина использует только ∃. Детерминированная имеет по одному возможному переходу. Альтернирование обобщает обе модели, не превращая универсальный узел в команду «запусти на реальных процессорах». Бесконечное оборудование не предполагается: это математическое правило принятия.

Почему AP содержится в PSPACE? При глубине дерева p(n) детерминированный обход хранит стек из p(n) кадров. Каждый кадр содержит полиномиально короткую конфигурацию, номер следующего потомка и промежуточный ответ. Произведение двух полиномов остаётся полиномом. Время обхода может быть экспоненциальным: экономится память, а не число посещённых листьев.

Обратное включение содержательнее. Граф конфигураций машины с полиномиальной памятью имеет экспоненциально много вершин. Проверять путь такой длины можно делением пополам: ∃ угадывает среднюю конфигурацию, ∀ выбирает, какую половину проверить. На одной ветви остаётся только одна половина на каждом уровне. Число уровней логарифмично от экспоненциальной длины пути, то есть полиномиально. Середина записывается полиномиальным числом бит. Именно выбор одной половины универсальной проверкой позволяет удержать время ветви в полиноме.

Если число переключений между блоками ∃ и ∀ ограничено константой, получаются уровни полиномиальной иерархии. Первый экзистенциальный уровень - NP, первый универсальный - coNP. Следующий экзистенциальный уровень имеет вид «существует короткий x, для любого короткого y выполняется полиномиально проверяемый предикат». AP разрешает полиномиально много переключений и в общем случае шире известного описания одним фиксированным уровнем.

Правило

Время альтернирующей машины - максимум длины ветви, а не сумма размеров всех ветвей. Универсальный узел требует успеха каждого ответа соперника. AP = PSPACE не означает P = PSPACE. В постановке задачи выписывай порядок кванторов: перестановка порядка меняет допустимую зависимость ходов.

Разбор: порядок кванторов меняет ответ

Файл вычисляет небольшие булевы игры полным обходом. Обёртка qbf принимает строку кванторов и проверяемое условие. В первом случае y выбирается после x; во втором x должен подойти ко всем значениям y сразу.

from itertools import product


def qbf(kvantory, uslovie):
    posecheno = [0]

    def idti(i, znacheniya):
        posecheno[0] += 1
        if i == len(kvantory):
            return bool(uslovie(*znacheniya))
        levyj = idti(i + 1, znacheniya + [False])
        pravyj = idti(i + 1, znacheniya + [True])
        if kvantory[i] == 'E':
            return levyj or pravyj
        if kvantory[i] == 'A':
            return levyj and pravyj
        raise ValueError('неизвестный квантор')

    otvet = idti(0, [])
    return otvet, posecheno[0]


def ravenstvo(x, y):
    return x == y


def vosstanovlenie(nastrojka, sboj, deistvie):
    return deistvie == (nastrojka != sboj)


for kv in ['AE', 'EA']:
    otvet, uzlov = qbf(kv, ravenstvo)
    print(kv, otvet, 'узлов', uzlov)
for kv in ['EAE', 'EEA']:
    # Во втором порядке второй аргумент - действие, третий - сбой.
    f = vosstanovlenie if kv == 'EAE' else (
        lambda n, d, s: vosstanovlenie(n, s, d))
    otvet, uzlov = qbf(kv, f)
    print(kv, otvet, 'узлов', uzlov)
print('строк стратегии для двух ответов соперника:', 2 ** 2)

AE True узлов 7
EA False узлов 7
EAE True узлов 15
EEA False узлов 15
строк стратегии для двух ответов соперника: 4

В ∀x ∃y: x = y ответ y подстраивается под выбранный x: достаточно повторить значение. В ∃x ∀y: x = y одно x должно совпасть с обоими значениями y, что невозможно. Программа посещает оба потомка даже там, где логический ответ уже известен, поэтому число узлов ровно соответствует полному двоичному дереву.

Разбор: глубина три, пятнадцать конфигураций

При трёх двоичных выборах дерево имеет 1 + 2 + 4 + 8 = 15 узлов. Одна партия содержит три выбора. Стек обхода хранит только текущий путь длины три, а не все пятнадцать узлов. При ста выборах число листьев 2¹⁰⁰, но глубина сто. Эта разница и объясняет, почему полиномиальное время ветви сочетается с мощностью полиномиальной памяти обычной машины.

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

Что ломается без этого

Если заменить AND узла на OR, программа проверит наличие одной удачной партии вместо выигрышной стратегии. Если считать суммарную работу дерева временем альтернирующей машины, потеряется определение AP. Если объявить независимые процессы «универсальными состояниями» без правила общего принятия, получится обычный параллелизм, а не эта модель.

Зачем это в работе

Проверка протокола с противником, синтез контроллера и анализ игр требуют вложенных «для любого» и «существует». Альтернирование позволяет узнать, почему короткая партия всё равно приводит к PSPACE-полной задаче. Для реализации чаще используется обход, решатель формул с кванторами или специализированная игра; теория объясняет ожидаемый расход ресурсов и опасность замены стратегии одним сертификатом.

Теперь сам

Истинно ли ∀x ∃y ∀z: (x = y) или z? Значения булевы, а последнее «или» - обычная дизъюнкция.