Теорема Сэвича: в памяти угадывание почти ничего не даёт

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

Как думаешь, можно ли искать путь, ничего не запоминая

Обход в ширину помечает вершины, в которых побывал: без пометок он ходил бы по кругу. Пометок столько, сколько вершин. В графе на миллиард вершин это миллиард бит.

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

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

Проверка длинного маршрута по частям. Чтобы убедиться, что из города A можно доехать до города B не больше чем за восемь перегонов, достаточно назвать город M посередине и проверить две половины по четыре перегона. Каждую половину проверяют так же, называя свою середину.

Записывать приходится только текущую цепочку вопросов: «A-B за восемь, значит A-M за четыре, значит A-K за два». Проверив левую половину, её записи стирают и на том же листке проверяют правую. Листок маленький; ходить по нему приходится много.

Механизм: середина пути и повторное использование памяти

Обозначим ПУТЬ(a, b, k) утверждение «из a в b есть путь длиной не больше 2ᵏ рёбер».

ПУТЬ(a, b, 0):    a = b  или  есть ребро из a в b
ПУТЬ(a, b, k):    существует вершина m такая, что
                  ПУТЬ(a, m, k − 1)   и   ПУТЬ(m, b, k − 1)

Путь короче 2ᵏ тоже годится: серединой годится любая вершина пути, от которой до обоих концов не больше 2ᵏ⁻¹ рёбер; у совсем короткого пути это сам конец b, и вторая половина окажется путём нулевой длины. В графе с n вершинами путь без повторов не длиннее n − 1, поэтому достижимость - это ПУТЬ(a, b, k) при 2ᵏ ≥ n, то есть k около log₂ n.

Алгоритм: перебирать все вершины m по очереди и для каждой проверять две половины рекурсивно.

Память. Глубина рекурсии - k + 1, около log n. На каждом уровне хранятся три номера вершин и k, каждый - log n бит. Всего порядка log² n бит. Обход в ширину хранит n пометок и очередь до n номеров вершин - порядка n log n бит.

Время. На каждом уровне перебираются n середин и делаются два вызова: число вызовов - до (2n)ᵏ, то есть n в степени порядка log n. Это больше любого многочлена.

Память мала потому, что две половины проверяются не одновременно, а по очереди: стек после первой половины освобождается и служит второй. Время велико по той же причине: результаты не запоминаются.

От графов к машинам. Возьмём недетерминированную машину с памятью s. Её конфигурации - вершины графа, возможные шаги - рёбра; вопрос «принимает ли она вход» - это вопрос о достижимости принимающей конфигурации из начальной. Чтобы принимающая конфигурация была одна, машину заставляют перед ответом стереть память и вернуть головки в начало. Вершин в этом графе до 2 в степени порядка s, так что log их числа - порядка s. Приём с серединами проверяет достижимость в памяти порядка s², причём граф хранить не нужно: конфигурации перебираются как числа, а ребро проверяется по таблице машины.

Теорема Сэвича. Всё, что недетерминированная машина решает в памяти s, детерминированная решает в памяти порядка s². Условие - s не меньше log n, где n - длина входа машины: положение головки на входе - тоже часть конфигурации, на его запись нужно log n бит, и при меньшей s счёт вершин выше неверен.

Квадрат многочлена - многочлен, поэтому недетерминированная полиномиальная память даёт тот же класс PSPACE. Со временем такой теоремы нет: лучшее известное моделирование угадывания по времени - экспонента.

Правило

Достижимость в графе с n вершинами проверяется в памяти порядка log² n: путь длины не больше 2ᵏ ищется перебором середины и рекурсией на две половины, которые проверяются по очереди на одной памяти. Отсюда теорема Сэвича: недетерминированная память s моделируется детерминированной памятью порядка s², и угадывание не расширяет PSPACE.

Разбор: путь из восьми вершин, найденный серединами

Граф - цепочка 0 → 1 → … → 7, рёбра направлены вперёд. Функция put_est проверяет ПУТЬ(a, b, k) и ведёт два счётчика: число вызовов и наибольшую глубину рекурсии. Для сравнения - обход в ширину, который возвращает ответ и число помеченных вершин.

def put_est(sosedi, a, b, k, schyot, glubina):
    schyot[0] = schyot[0] + 1
    if glubina > schyot[1]:
        schyot[1] = glubina
    if a == b:
        return True
    if k == 0:
        return b in sosedi[a]
    for seredina in range(len(sosedi)):
        if put_est(sosedi, a, seredina, k - 1, schyot, glubina + 1):
            if put_est(sosedi, seredina, b, k - 1, schyot, glubina + 1):
                return True
    return False

def obhod(sosedi, a, b):
    videli = [False] * len(sosedi)
    videli[a] = True
    ochered = [a]
    i = 0
    while i < len(ochered):
        v = ochered[i]
        i = i + 1
        for u in sosedi[v]:
            if not videli[u]:
                videli[u] = True
                ochered.append(u)
    return [videli[b], len(ochered)]

cep = []
for v in range(8):
    cep.append([])
for v in range(7):
    cep[v].append(v + 1)
schyot = [0, 0]
print(put_est(cep, 0, 7, 3, schyot, 1), schyot, obhod(cep, 0, 7))
schyot = [0, 0]
print(put_est(cep, 7, 0, 3, schyot, 1), schyot, obhod(cep, 7, 0))

True [417, 4] [True, 8]
False [658, 4] [False, 1]

Путь из 0 в 7 найден: 417 вызовов при глубине 4. Обход в ширину пометил восемь вершин и закончил. Обратного пути нет: рекурсия убедилась в этом за 658 вызовов, обход - сразу, пометив одну вершину.

По времени рекурсия проигрывает безнадёжно, и с ростом графа разрыв растёт быстрее любого многочлена. По памяти картина обратная. Глубина 4 - это k + 1; на каждом уровне три номера вершин. Для графа на миллион вершин глубина была бы двадцать один, и вся память - шестьдесят с небольшим номеров по двадцать бит. Обход хранил бы миллион пометок.

На восьми вершинах это не впечатляет: двенадцать номеров против восьми пометок. Приём создан для графов, которые нельзя ни записать, ни пометить, - таких, как граф конфигураций.

Разбор: сколько это даёт для машин

Посчитаем для недетерминированной машины с s клетками памяти над двумя символами; положение головки на входе для простоты не учитываем - оно добавляет к номеру конфигурации ещё log n бит.

память машины s    30 клеток              100 клеток
конфигураций       порядка 2³⁰ · 30       порядка 2¹⁰⁰ · 100
обход с пометками  миллиарды бит          10³² бит: не поместится нигде
середины: глубина  около 35               около 107
          уровень  три конфигурации       три конфигурации
          всего    около 3 · 35 · 35 бит  около 3 · 107 · 107 бит
                   ≈ 3,7 тысячи бит       ≈ 34 тысячи бит

Глубина 35 - это логарифм числа конфигураций, log₂(2³⁰ · 30) ≈ 35; столько же бит занимает номер одной конфигурации, отсюда 3 · 35 · 35. Множитель 30 в числе конфигураций - положение головки на рабочей памяти.

Граф из 2¹⁰⁰ вершин нельзя ни построить, ни обойти с пометками. А рекурсия по серединам просматривает его, держа в памяти около тридцати четырёх тысяч бит. Время при этом - 2 в степени порядка s², то есть для ста клеток совершенно недостижимое; но теорема говорит о памяти, и про память она точна.

Почему тот же трюк не доказывает, что P = NP? Он обменивает время на память, а не наоборот. Чтобы убрать угадывание из времени, нужно было бы находить середину, не перебирая всех кандидатов. Памяти перебор не стоит ничего: кандидаты сменяют друг друга на одном месте. Времени он стоит всё.

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

Приём берут вместо обхода в обычной задаче. Время n в степени log n на графе в тысячу вершин - это 10³⁰. Рекурсия по серединам - доказательство возможности, а не рабочий алгоритм.

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

Ждут такой же теоремы для времени. Память переиспользуется, время - нет. В этом вся разница между решённым вопросом о памяти и открытым вопросом о времени.

Считают, что квадрат - это всегда мало. Для логарифмической памяти квадрат выводит из класса: log² n - уже не log n. Совпадают ли L и NL, теорема не говорит.

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

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

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

Оценка «а поместится ли». Вопрос о памяти отделён от вопроса о времени, и отвечать на него надо отдельно: задача может быть безнадёжной по времени и лёгкой по памяти, и наоборот.

Теперь сам

1. В графе 1024 вершины. Какое k нужно взять и какова глубина рекурсии?
2. Сколько номеров вершин хранится в стеке при проверке достижимости в таком графе?
3. Почему две половины пути можно проверять на одной и той же памяти?
4. Недетерминированная машина работает в памяти n³. В какой памяти её моделирует детерминированная?
5. Почему из теоремы Сэвича не следует, что L = NL?