Конспект: память как ресурс, PSPACE, L, NL и иерархии

Понятия

Память алгоритма - наибольшее число одновременно занятых клеток, не считая входа.

PSPACE - задачи, решаемые в полиномиальной памяти при любом времени. L - в памяти порядка log n при входе только для чтения. NL - то же с угадыванием. EXP - за экспоненциальное время.

Теорема Сэвича - недетерминированная память s моделируется детерминированной порядка s².

Формула с кванторами - КНФ, где каждая переменная связана словом ∃ или ∀. Задача об её истинности полна для PSPACE.

Теоремы об иерархии - заметно больший запас времени или памяти даёт строго больше решаемых задач.

Что унести

ДВА НЕРАВЕНСТВА
память ≤ время                          за шаг - одна клетка
время ≤ число конфигураций ≈ 2 в степени порядка памяти
                                        иначе повтор и вечный цикл

L  ⊆  NL  ⊆  P  ⊆  NP  ⊆  PSPACE  ⊆  EXP
NP ⊆ PSPACE:  сертификаты перебираются на одном месте
перебор наборов:   16, 256, 4096 наборов  при  4, 8, 12 битах памяти

сумма подмножества:        действий      клеток
  таблица, малые числа        472           78
  таблица, числа × 50       23208         3851
  перебор, любые числа       2048            5

СЭВИЧ: достижимость без пометок
ПУТЬ(a, b, k)  =  существует m:  ПУТЬ(a, m, k − 1)  и  ПУТЬ(m, b, k − 1);
                  2ᵏ ≥ n
глубина log n,  на уровне три номера вершин  →  память log² n;
                время n в степени log n
цепочка из 8 вершин:  417 вызовов, глубина 4;   обход - 8 пометок
половины проверяются ПО ОЧЕРЕДИ на одной памяти - в этом весь выигрыш

граф конфигураций машины с памятью s:  2 в степени s вершин → память s²
недетерминированная PSPACE = PSPACE;     для времени такой теоремы нет

КВАНТОРЫ И ИГРЫ
∃x: «или» двух ветвей      ∀x: «и» двух ветвей      память n, время 2ⁿ
формула x = y:    ∃∃ истинна    ∀∃ истинна    ∃∀ ложна    ∀∀ ложна
                  порядок кванторов = порядок ходов

позиция выигрышна  ⇔  есть ход в проигрышную для противника
камни, ходы 1, 3, 4:   ПВПВВВВ ПВПВВВВ П …  период 7
без запоминания вызовов:  68, 545, 2184, 8738  при  10, 14, 18, 22 камнях
полны для PSPACE:  формулы с кванторами, игра в города на графе,
                   гекс, реверси на доске n × n
сертификат выигрыша - дерево ответов, а не ход

ЛОГАРИФМИЧЕСКАЯ ПАМЯТЬ
можно:   несколько указателей на вход,  счётчики до многочлена,
         перечитывать вход
нельзя:  копировать вход,  помечать элементы,  держать стек длиной n

палиндром двумя указателями:   длина 8 → 4096;   указатели 6 → 24 бит;
                               копия 64 → 32768 бит
NL: достижимость - угадывать следующую вершину,
    помнить текущую и счётчик;  полна для NL
случайное блуждание: одна вершина и счётчик;  предел 2 · m · (n − 1);
                     «дошёл» верно всегда
NL = co-NL доказано;   L = NL? неизвестно;
неориентированная достижимость лежит в L

ИЕРАРХИИ И КАРТА
диагональ с будильником:  моделировать M на её коде не дольше f шагов
                          и ответить наоборот
доказано:      P ≠ EXP      L ≠ PSPACE      NL ≠ PSPACE
неизвестно:    L = NL?   NL = P?   P = NP?   NP = PSPACE?   PSPACE = EXP?

L         палиндром, подсчёт, работа ДКА
NL        достижимость, 2 литерала в скобке
P         пути, потоки, паросочетания, разбор, линейное программирование
NP        выполнимость, клика, раскраска, коммивояжёр с порогом
PSPACE    формулы с кванторами, игры, равенство двух НКА
EXP       шахматы на доске n × n
дальше    проблема останова

Ловушки джокера

Считал только время. Память кончается раньше и жёстче.

Включил вход в рабочую память. Тогда меньше n не бывает, и чтение не отличить от копирования.

Решил, что малая память означает скорость. Она ограничивает время только сверху, экспонентой.

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

Перенёс теорему Сэвича на время. Время нельзя использовать дважды.

Переставил кванторы. ∀x ∃y и ∃y ∀x - разные утверждения.

Принял ход за стратегию. Выигрыш - это ответ на каждый ход противника.

Обошёл список рекурсией «в логарифмической памяти». Стек глубиной n - это n памяти.

Сослался на иерархию как на доказательство P ≠ NP. Она сравнивает количество одного ресурса.

Проверь себя

Почему NP ⊆ PSPACE и PSPACE ⊆ EXP? Как проверить достижимость без пометок и сколько это стоит по памяти и по времени? Почему порядок кванторов важен и как игра превращается в формулу? Что разрешено в логарифмической памяти? Какие разрывы между классами доказаны и почему тем же способом не разделить P и NP?

NL = coNL (Иммерман-Селепчени): отрицание достижимости проверяется индуктивным счётом слоёв; число подтверждённых разных вершин должно точно совпасть с известным размером.

Альтернирование: узлы ∃ принимают по OR, ∀ по AND. Время измеряется длиной ветви; AP = PSPACE. Постоянное число чередований даёт уровни полиномиальной иерархии.

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий