Конспект раздела: что вообще вычислимо

Одна мысль на весь раздел

У вычислений есть границы, и они разного рода. Одни - о памяти модели: автомат не считает, стек не сравнивает три количества. Другие - о самой возможности: на вопрос об останове не отвечает ни одна программа. Третьи - о цене: задача решается, но, по всей видимости, не быстро. Первые два рода границ доказаны. Третий стоит на одном недоказанном предположении, P ≠ NP, и на тысячах задач, которые к нему привязаны.

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

Как части связаны

конечный автомат      регулярные языки;  aⁿbⁿ не принимает
   │ + стек           равенство разрешимо (обход пар состояний)
   ▼
магазинный автомат    КС-языки;  aⁿbⁿcⁿ не принимает
   │ + лента          равенство неразрешимо (сводится задача Поста)
   ▼
машина Тьюринга       всё вычислимое;  дальше модели не усиливаются
   │                  программа = данные: универсальная машина
   ▼
третий исход: не остановиться
   │
   ▼
диагональ ──┬──► проблема останова неразрешима
            │        └─► сведения: домино Поста, уравнения в целых
            │                      числах, однозначность грамматик
            ├──► теорема Райса: поведение программ не проверить точно
            └──► иерархии: P ≠ EXP,  L ≠ PSPACE

время:   P ────────► NP ────────► NP-полные: SAT → 3-SAT →
         решить      проверить    независимое множество → …
                                  сведение: «не труднее»
память:  L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP   память возвращается,
                                          время нет
кванты:  P ⊆ BQP ⊆ PSPACE      период: без кванта полином неизвестен;
                               поиск - корень

Что выбрать

задача                            инструмент
формат без вложенности            автомат, регулярное выражение;
                                  движок без возвратов
вложенность, выражения            грамматика, рекурсивный спуск
согласование трёх мест,           программа: проход после разбора
имён, копий
«равны ли два автомата»           обход пар состояний - точный ответ
«остановится ли»,                 точного ответа нет: надёжный анализатор
«делает ли программа X»           с ложными тревогами или предел времени
задача из каталога NP-полных      малые входы - перебор; малые числа -
                                  таблица; особая структура - частный
                                  алгоритм; иначе - раздел 22
игра, «для любого ответа          перебор с отсечениями;
противника»                       короткий сертификат неизвестен
данные не помещаются в память     указатели, счётчики,
                                  случайное блуждание
шифр со сроком тайны              постквантовые алгоритмы;
больше десяти лет                 симметричным - длинный ключ

Числа раздела, которые стоит помнить

k-й символ с конца: НКА k + 1 состояние, ДКА 2ᵏ
(a+)+b на 24 буквах - секунда, дальше вдвое
CYK: 21 824 проверки на 32 скобках; стек - 32 шага
деревьев разбора: 1 2 5 14 42 132 429
машина для aⁿbⁿcⁿ: 23 77 281 1073 4193 шага
BB: 1 6 21 107 47 176 870
2ⁿ при миллиарде (≈ 2³⁰) операций в секунду: n = 40 - 17 минут;
                                     60 - 34 года;  80 - 35 миллионов лет
простых путей в решётке: 2 12 184 8512
таблица сумм: числа × 4 - работа × 4
Гровер: 64 варианта - 6 шагов; (π/4) · √N
Шор: 15 = 3 · 5 через период 4

Границы, общие для всех результатов

всё здесь - про худший случай        конкретный вход трудной задачи
                                     бывает лёгким
«нет алгоритма» - только для         для отдельной программы, набора
общего случая                        костей, формулы ответ находится
                                     рассуждением или перебором
направление сведения                 известная трудная задача сводится
                                     К новой, не наоборот
длина входа - биты записи            время от величины числа -
                                     псевдополином
модель не меняет вычислимого         ленты, стеки, кванты меняют
                                     только скорость
недоказанное называется              P ≠ NP, NP ≠ PSPACE, «NP не в BQP» -
недоказанным                         ожидания, а не теоремы

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

Разбирал вложенную структуру регулярным выражением. Работает до глубины, на которую рассчитано.

Принял «не остановилась» за «нет». Третий исход - не ответ.

Заменил «не знаю» на «нет» по тайм-ауту. Ошибка случится там, где проверка была нужнее всего.

Свёл не в ту сторону. К трудной задаче сводится всё; трудность доказывает обратное сведение.

Прочитал NP как «неполиномиальные». В NP лежит и сортировка.

Назвал NP-полную задачу неразрешимой. Она решается перебором; открыт только вопрос о скорости.

Посчитал время от величины числа. Таблица на n · S клеток - экспонента от длины записи S.

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

Перенёс теорему о памяти на время. Память используется повторно, время нет.

Счёл квантовый компьютер перебором всех вариантов сразу. Измерение даёт один исход.

Как меняется модель вычислений

Задача	Инструмент	Условие или граница
Состояния и самоописание	Минимизация ДКА, теорема о рекурсии	Различимость состояний и тотальность преобразования проверяются отдельно.
Случайность	BPP, RP, coRP, ZPP	Различай направление ошибки и ожидаемое время.
Совет и взаимодействие	P/poly и IP	Неравномерное семейство схем не обязано иметь эффективный генератор; IP=PSPACE.
Пространство и чередование	NL=coNL, AP=PSPACE	Время альтернирования считается по длине ветви, не по всему дереву.
Сходные названия задач	Изоморфизм, упаковка, надстрока	Точно определи сертификат и постановку перед переносом оценки.

Проверь, что можешь объяснить

Почему ни один конечный автомат не принимает aⁿbⁿ и чем этот довод похож на довод про aⁿbⁿcⁿ? Что значит «модель вычислений не меняет вычислимого»? Как устроена программа, которая делает наоборот, и почему её нельзя обойти более умной проверкой? Чем сертификат отличается от решения и почему у ответа «нет» его может не быть? Какие два шага доказывают NP-полноту? Почему NP ⊆ PSPACE? Что из границ раздела сдвигает квантовая машина и что оставляет на месте?