Иерархии и карта классов: что доказано, а что нет

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

Как думаешь, даёт ли что-нибудь лишнее время

Алгоритму разрешили работать не n² шагов, а n³. Очевидно, что он успеет больше прежнего.

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

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

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

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

Механизм: диагональ с будильником

Теорема об иерархии по времени. Если функция g растёт заметно быстрее f - достаточно, чтобы g превосходила f · log f, - то существует задача, которая решается за время порядка g и не решается за время порядка f. Логарифм - цена моделирования: на один шаг чужой машины универсальная тратит порядка log f своих - лент у чужой машины может быть сколько угодно, а у универсальной их число постоянно; эту оценку принимаем без доказательства. Для памяти то же, и запас нужен меньше: достаточно, чтобы g росла быстрее f. Обе теоремы верны для обычных границ - логарифмов, степеней, экспонент; для экзотических функций нужны оговорки.

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

машина D на входе - описании машины M:
    моделировать M на её собственном описании,
        пока хватает запаса времени g
    если M успела принять         →  отвергнуть
    если M отвергла или не успела →  принять

D всегда останавливается: будильник не даст ей зациклиться, и её время - в пределах g. Запас считается от длины входа, то есть описания M. И D отличается от любой машины M, которая работает за время порядка f: описаний у машины бесконечно много - в таблицу можно дописывать лишние строки, - и на достаточно длинном из них M успевает ответить до будильника, потому что g растёт быстрее f с запасом на моделирование. А D на этом описании отвечает наоборот. Значит, язык D не распознаёт ни одна машина со временем f.

Следствия.

P ≠ EXP        многочлен против экспоненты: запаса с избытком
L ≠ PSPACE     логарифм против многочлена
NL ≠ PSPACE    по теореме Сэвича NL решается в памяти log² n,
               а её от многочлена отделяет иерархия

Карта.

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP ⊂ разрешимые ⊂ распознаваемые
             и co-NP между P и PSPACE

доказано:     L ≠ PSPACE,   NL ≠ PSPACE,   P ≠ EXP,   NL = co-NL,
              недетерминированная PSPACE = PSPACE
неизвестно:   L = NL?   NL = P?   P = NP?   NP = co-NP?
              NP = PSPACE?   PSPACE = EXP?

Значок ⊂ - строгое включение: эти два неравенства доказаны в главе о неразрешимости. Раз P ≠ EXP, хотя бы одно из включений P ⊆ NP ⊆ PSPACE ⊆ EXP строгое. Большинство исследователей полагает, что строгие все. Доказательства нет ни для одного.

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

Правило

Теоремы об иерархии: заметно больший запас времени или памяти позволяет решить строго больше задач; доказываются диагональю с ограничением ресурса. Следствия: P ≠ EXP, L ≠ PSPACE. В цепочке L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP хотя бы одно включение строгое, но ни про одно соседнее это не доказано. Иерархии сравнивают количество одного ресурса и не сравнивают разные ресурсы.

Разбор: диагональ при трёх запасах времени

Пять машин в формате главы о машине Тьюринга; функция v_bity оттуда же кодирует описание машины нулями и единицами, по три бита на символ. Функция za_vremya отвечает, успела ли машина принять вход за predel шагов. Для каждого запаса времени строится диагональный язык D: «машина не приняла собственный код за отведённое время».

def za_vremya(opisanie, vhod, predel):
    tabl = {}
    for pravilo in opisanie.split(" "):
        tabl[pravilo[0] + pravilo[1]] = [pravilo[2], pravilo[3],
                                         pravilo[4]]
    lenta = list(vhod)
    sostoyanie = "0"
    poz = 0
    shagov = 0
    while sostoyanie != "+":
        klyuch = sostoyanie + lenta[poz]
        if klyuch not in tabl or shagov == predel:
            return False
        hod = tabl[klyuch]
        lenta[poz] = hod[0]
        if hod[1] == "R":
            poz = poz + 1
            if poz == len(lenta):
                lenta.append("_")
        elif poz > 0:
            poz = poz - 1
        sostoyanie = hod[2]
        shagov = shagov + 1
    return True

def v_bity(tekst):
    alfavit = "012_+RL "
    bity = ""
    for simvol in tekst:
        nomer = 0
        while alfavit[nomer] != simvol:
            nomer = nomer + 1
        bity = (bity + str(nomer // 4) + str(nomer // 2 % 2)
                + str(nomer % 2))
    return bity

mashiny = ["010R0 001R+ 0_1R+", "000R0 011R1 100R1 110R0 0__R+",
           "000R0 011R1 100R1 110R0 1__R+"]
mashiny = mashiny + ["000R0 011R1 111R1 100R0 1__R+", "011R+ 001R+"]
for predel in [5, 50, 500]:
    diagonal = []
    for m in mashiny:
        diagonal.append(not za_vremya(m, v_bity(m), predel))
    print(predel, diagonal)

5 [False, True, True, True, False]
50 [False, True, True, True, False]
500 [False, False, False, True, False]

Первая и последняя машины принимают свой код за один-два шага, и при любом запасе диагональ отвечает на них «нет». Четвёртая, «последний знак - единица», отвергает свой код - диагональ отвечает «да».

Вторая и третья машины считают чётность единиц и должны прочитать весь свой код, около девяноста бит. При запасе 5 и 50 они не успевают, и диагональ записывает им «да». При запасе 500 успевают, обе принимают - и диагональ меняет ответ на «нет».

Так и устроена теорема, только в ней диагональ определена на кодах всех машин сразу; пять машин здесь - окно в бесконечную таблицу. Язык D при запасе 500 - конкретный язык, и вычисляется он за пятьсот шагов моделирования на машину. От второй машины он отличается на её собственном коде, от третьей - на её. От любой машины, которая укладывается в запас, он отличается хотя бы в одной точке. А машины, которым запаса не хватает, в расчёт не идут: теорема говорит только о тех, кто работает быстро.

Разбор: кто на какой ступени

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

def konfiguracij(sostoyanij, kletok, simvolov):
    return sostoyanij * kletok * simvolov ** kletok

for kletok in [4, 8, 16, 32]:
    print(kletok, konfiguracij(10, kletok, 2))
for n in [16, 256, 65536]:
    bit = 0
    m = n
    while m > 1:
        bit = bit + 1
        m = m // 2
    print(n, bit, konfiguracij(10, bit, 2))

4 640
8 20480
16 10485760
32 1374389534720
16 4 640
256 8 20480
65536 16 10485760

Первые четыре строки: память растёт вдвое - число конфигураций возводится в квадрат, с поправкой. Точнее, конфигураций 10 · s · 2ˢ при s клетках: в квадрат возводится множитель 2ˢ - 16, 256, 65 536. Это PSPACE ⊆ EXP. Последние три: если память - логарифм длины входа, конфигураций получается многочлен: для входа длины 65 536 при шестнадцати клетках - десять миллионов, порядка n · log n на состояние. Это L ⊆ P.

Теперь расставим по ступеням задачи, которые встречались в курсе.

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

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

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

«Иерархия доказывает, что P ≠ NP». Иерархия сравнивает больше и меньше одного ресурса. P и NP отличаются не количеством времени, а наличием угадывания.

«Все включения строгие» выдают за факт. Это общее ожидание. Доказаны только разрывы между далёкими классами.

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

Запас «в два раза больше» считают достаточным. По времени постоянный множитель ничего не даёт: машину можно ускорить в постоянное число раз, укрупнив её алфавит, поэтому 2f и f - один и тот же запас. Нужен рост по порядку величины.

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

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

Чтение новостей. «Доказано, что класс A не равен классу B» - редкое и крупное событие; «найден алгоритм, решающий NP-полную задачу на практических входах» - обычная инженерная новость. Различать их помогает карта: первое меняет её, второе нет.

Честность в оценках. Фраза «это, скорее всего, нельзя решить быстро» точнее фразы «это нельзя решить быстро». За первой - полвека неудачных попыток, за второй - теорема, которой пока нет.

Теперь сам

1. Что утверждает теорема об иерархии по времени для n² и n³?
2. Зачем диагональной машине будильник?
3. Какие три неравенства между классами цепочки от L до EXP доказаны?
4. Из P ≠ EXP следует, что строгое хотя бы одно из трёх включений. Каких?
5. Машина работает в памяти log₂ n при n = 1024, два символа, 10 состояний. Сколько у неё конфигураций, не считая положения головки на входе?