Память против времени: ресурс, который можно использовать повторно

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

Как думаешь, сколько памяти нужно перебору

Перебор всех наборов значений для формулы из сорока переменных - это 2⁴⁰, больше триллиона наборов. Работать он будет долго.

Ответь себе до чтения: а сколько памяти ему нужно? Сорок бит. Наборы не нужно хранить все сразу: один проверили - на том же месте записали следующий. Время тратится безвозвратно, память освобождается. Экспоненциально долгое вычисление умещается на клочке бумаги, и это не курьёз, а основа отдельной шкалы трудности, на которой задачи выстраиваются иначе, чем по времени.

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

Школьная доска и урок. Урок кончается, и вернуть его нельзя. Доску вытирают и пишут заново: за день на одной доске помещается в сто раз больше, чем на ней есть места.

Считать «сколько доски нужно» и «сколько уроков нужно» - две разные бухгалтерии. Бывают выкладки на всю доску за пять минут и выкладки на полдоски на весь семестр.

Механизм: два неравенства и цепочка классов

Память алгоритма - наибольшее число клеток, занятых одновременно, как функция длины входа n. Сам вход в счёт не идёт: он лежит отдельно и только читается. Это позволяет говорить о памяти меньше длины входа.

Время ограничивает память. За t шагов машина успевает побывать не больше чем в t клетках: память не превосходит времени.

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

n  ·  число состояний  ·  s  ·  (число символов) в степени s

Множитель n - положение головки на входе, множитель s - на рабочей памяти. При памяти не меньше log n каждый из четырёх множителей не больше 2 в степени c · s для некоторой постоянной c (в частности, n = 2 в степени log n), и всё произведение - экспонента от s. Если машина без угадывания останавливается, конфигурации не повторяются: повтор означал бы вечный цикл. У машины с угадыванием то же верно для самого короткого удачного пути: будь на нём повтор, кусок между повторами можно было бы вырезать. Значит, время работы - у машины с угадыванием время кратчайшего удачного пути - не больше числа конфигураций, экспоненты от памяти.

Классы. Класс PSPACE - задачи разрешения, которые решаются в полиномиальной памяти; время при этом не ограничено. Он и остальные классы цепочки:

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

Из этих соображений получается цепочка:

L  ⊆  NL  ⊆  P  ⊆  NP  ⊆  PSPACE  ⊆  EXP

Логарифмическая память даёт полиномиальное число конфигураций - отсюда L ⊆ P. Для NL ⊆ P довод тот же с одним добавлением: принимает ли машина с угадыванием - это вопрос, достижима ли принимающая конфигурация из начальной, а конфигураций полиномиально много. В графе, где вершины - конфигурации, а ребро - один шаг машины, обход отвечает на этот вопрос за полиномиальное время. Полиномиальная память даёт экспоненциальное число - отсюда PSPACE ⊆ EXP. А NP ⊆ PSPACE - это перебор сертификатов на одном и том же месте: сертификат полиномиальной длины, проверка полиномиальна, память переиспользуется.

О строгости включений известно мало. Доказано, что L ≠ PSPACE и P ≠ EXP - это теоремы об иерархии из последнего урока главы; значит, где-то в цепочке включения строгие. Про каждое отдельное соседнее включение неизвестно, строгое ли оно.

Правило

Память алгоритма - наибольшее число одновременно занятых клеток, не считая входа. Память не превосходит времени; время останавливающейся машины не превосходит числа конфигураций, то есть экспоненты от памяти. Отсюда L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP. Перебор сертификатов переиспользует память, поэтому NP ⊆ PSPACE.

Разбор: экспонента времени на линейной памяти

Функция vypolnima проверяет формулу, перебирая наборы. Главная часть её рабочей памяти - счётчик kod из n бит: он и есть текущий набор. Остальное - счётчик наборов для отчёта и несколько номеров для обхода формулы. Возвращаются ответ, число просмотренных наборов и длина набора в битах - это расчёт главной части памяти, а не замер всей. Формула - невыполнимая цепочка, чтобы перебор дошёл до конца.

def vypolnima(formula, n):
    naborov = 0
    for kod in range(2 ** n):
        naborov = naborov + 1
        goditsya = True
        for skobka in formula:
            est = False
            for literal in skobka:
                if (literal > 0) == (kod >> (abs(literal) - 1) & 1 == 1):
                    est = True
            if not est:
                goditsya = False
                break
        if goditsya:
            return [True, naborov, n]
    return [False, naborov, n]

for n in [4, 8, 12]:
    cepochka = [[1]]
    for i in range(1, n):
        cepochka.append([-i, i + 1])
    cepochka.append([-n])
    print(vypolnima(cepochka, n))

[False, 16, 4]
[False, 256, 8]
[False, 4096, 12]

Наборов 16, 256, 4096 - время растёт вдвое на каждую переменную. Память под набор - 4, 8, 12 бит: растёт на один бит на переменную. Счётчик naborov - измерительный прибор, а не часть алгоритма; без него остаются несколько счётчиков для обхода формулы, по логарифму её длины каждый.

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

Разбор: один вопрос, два способа платить

Сумма подмножества из прошлой главы. Таблица достижимых сумм платит памятью: массив на S + 1 клетку. Перебор подмножеств платит временем: 2ⁿ масок, зато память - пять переменных: маска на n бит и ещё четыре - индекс, сумма, счётчик действий и отметка «найдено»; запись каждой растёт как длина входа, а не как 2ⁿ. Функции возвращают ответ, число действий и размер памяти: у таблицы - число клеток массива, у перебора - число переменных, вписанное рукой. Единицы разные, сравнивать стоит порядок роста.

def tablicej(chisla, cel):
    dostizhimo = [False] * (cel + 1)
    dostizhimo[0] = True
    shagov = 0
    for x in chisla:
        for s in range(cel, x - 1, -1):
            shagov = shagov + 1
            if dostizhimo[s - x]:
                dostizhimo[s] = True
    return [dostizhimo[cel], shagov, cel + 1]

def pereborom(chisla, cel):
    shagov = 0
    najdeno = False
    for maska in range(2 ** len(chisla)):
        summa = 0
        for i in range(len(chisla)):
            shagov = shagov + 1
            if maska >> i & 1 == 1:
                summa = summa + chisla[i]
        if summa == cel:
            najdeno = True
    return [najdeno, shagov, 5]

malye = [3, 5, 9, 14, 20, 27, 33, 41]
print(tablicej(malye, 77), pereborom(malye, 77))
bolshie = []
for x in malye:
    bolshie.append(x * 50)
print(tablicej(bolshie, 3850), pereborom(bolshie, 3850))

[True, 472, 78] [True, 2048, 5]
[True, 23208, 3851] [True, 2048, 5]

На малых числах таблица выигрывает по времени, 472 действия против 2048, и занимает 78 клеток против пяти переменных. Когда числа выросли в пятьдесят раз, таблица стала делать 23 208 действий и занимать 3851 клетку, а перебор не заметил разницы: те же 2048 действий и пять переменных.

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

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

Считают только время. Алгоритм с хорошей оценкой времени падает с нехваткой памяти на первом настоящем входе. Память - ограничение жёсткое: её либо хватает, либо нет.

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

«Малая память - значит, быстро». Наоборот: малая память ограничивает время только сверху, и часто цена экономии памяти - экспонента времени.

«PSPACE - это про огромную память». Это полиномиальная память при неограниченном времени. Класс содержит NP и, вероятно, строго больше.

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

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

Потоковая обработка. Алгоритмы прошлого раздела - счётчики, наброски, выборки - это вычисления в памяти намного меньше входа. Теория малой памяти говорит, что в таком режиме возможно в принципе.

Глубина рекурсии. Стек вызовов - тоже память. Перебор с возвратом хранит один путь, а не всё дерево, и потому умещается там, где обход в ширину не поместился бы.

Теперь сам

1. Формула из шестидесяти переменных проверяется перебором. Сколько бит нужно под текущий набор и сколько наборов придётся просмотреть в худшем случае?
2. У машины 20 клеток рабочей памяти, два символа, 5 состояний. Оцени сверху число её конфигураций, не учитывая положение головки на входе.
3. Почему NP ⊆ PSPACE?
4. Алгоритм работает в памяти порядка log n. Что можно сказать о времени его работы, если он останавливается?
5. Между какими парами классов цепочки неравенство доказано?