Формальные языки
Варианты машин Тьюринга
Почему P vs NP - открытый вопрос? Интуиция: НМТ 'угадывает' правильный ответ за poly(n). Детерминированная симуляция угадывания - это перебор 2^O(n) вариантов. P = NP спрашивает: есть ли детерминированный способ 'угадывать' так же быстро? Оказывается, ответ зависит от того, какими инструментами мы доказываем - и большинство известных инструментов принципиально не подходят.
- **SAT-солверы (CDCL):** Z3, MiniSAT, CaDiCaL решают NP-полные задачи в промышленности. Они симулируют НМТ через умный backtracking с обучением на конфликтах. Применяются в верификации чипов Intel, формальной верификации протоколов
- **GPU как parallel НМТ:** CUDA выполняет тысячи потоков параллельно - это аппроксимация параллельного обхода дерева НМТ. Для задач с хорошей параллельной структурой даёт огромное ускорение
- **Квантовые компьютеры:** QTM (квантовая МТ) суперпозиционирует все ветви вычисления одновременно. BQP - квантовый аналог P. Алгоритм Гровера решает задачу поиска за O(√N) вместо O(N)
- **Рандомизированные алгоритмы:** Miller-Rabin (проверка простоты), QuickSort (рандомизированный pivot) - вероятностные МТ. BPP - класс задач, решаемых за poly с ошибкой < 1/3
Многоленточная МТ
Стандартная МТ имеет одну ленту. Реальные компьютеры имеют регистры, RAM, кэш - несколько «лент». **k-ленточная МТ** имеет k лент с независимыми головками. На каждом шаге: читать k символов, записать k символов, сдвинуть k головок. Это удобнее для программирования - и не даёт никакого прироста вычислительной мощности.
**Теорема:** любая k-ленточная МТ, работающая за t(n) шагов, может быть симулирована однолепточной МТ за O(t(n)²) шагов. Симуляция: содержимое k лент кодируется на одной ленте разделителями #, головки отмечаются маркерами. За один шаг однолепточная МТ совершает O(t(n)) движений для синхронизации всех «виртуальных голов».
k-ленточная МТ работает за t(n) шагов. Сколько шагов нужно для симуляции однолепточной МТ?
Недетерминированная МТ (НМТ)
**Недетерминированная МТ** в каждом состоянии может выбрать один из нескольких переходов. Вычисление - не цепочка конфигураций, а **дерево** конфигураций. НМТ принимает w, если хотя бы одна ветвь дерева достигает q_accept. Это абстракция «угадывания правильного ответа» - ключевая концепция для класса NP.
**Теорема:** любая НМТ, работающая за t(n) шагов, симулируется детерминированной МТ за 2^O(t(n)) шагов. Ключевая идея: дерево вычислений НМТ глубиной t(n) имеет не более 2^t(n) листьев. Детерминированная симуляция обходит все ветви через dovetailing (BFS). Это замедление - основа гипотезы P ≠ NP.
НМТ принимает язык L за t(n) шагов. Что можно сказать о L?
МТ с оракулом
МТ с **оракулом** для языка B может за один шаг проверить, принадлежит ли строка B - независимо от сложности этой проверки. Оракул - «чёрный ящик» без ограничений по времени. Это инструмент для изучения относительной сложности: M^B читается «МТ M с оракулом для B».
Результат Бейкера-Гилла-Соловея (1975): существуют оракулы A и B такие, что P^A = NP^A, но P^B ≠ NP^B. Это означает: любое доказательство P = NP или P ≠ NP должно быть **не релятивизируемым** - не работать одинаково для всех оракулов. Большинство известных техник доказательств релятивизируемы, что объясняет трудность вопроса P vs NP.
Почему результат о существовании оракулов A,B с P^A=NP^A и P^B≠NP^B важен для P vs NP?
Эквивалентность вариантов МТ
Все разумные варианты МТ **эквивалентны по вычислимости** - распознают один и тот же класс языков. Различия только в эффективности. Это одно из проявлений тезиса Чёрча-Тьюринга: не важно какую модель вычислений выбрать, граница «вычислимо/невычислимо» одна и та же.
| Вариант МТ | Замедление симуляции однолепточной | Класс сложности |
|---|---|---|
| k-ленточная | O(t(n)²) | Без изменения вычислимости |
| Недетерминированная | 2^O(t(n)) | NTIME(t(n)) vs DTIME(2^t(n)) |
| Двусторонняя лента | O(t(n)) | Без изменений |
| МТ с оракулом A | O(t(n)) | Класс P^A, NP^A |
| Вероятностная МТ | Poly симуляция | BPP ⊆ PSPACE |
| Квантовая МТ | Не известно | BQP - отдельный класс |
**Практический вывод:** при доказательстве разрешимости/неразрешимости можно свободно использовать многоленточные и недетерминированные МТ - это не меняет вывод. При доказательстве сложности (P, NP, PSPACE) нужно быть осторожным: переход от НМТ к ДМТ стоит экспоненциального замедления.
Недетерминированная МТ нереалистична - в реальных компьютерах нет недетерминизма
НМТ - теоретический инструмент для определения класса NP. Реализуется через параллельные вычисления, backtracking, или угадывание с верификацией
Класс NP определяется через НМТ: задача в NP если НМТ решает её за полиномиальное время. Эквивалентное определение: задача в NP если решение проверяется детерминированно за полиномиальное время. SAT-солверы (CDCL) реализуют детерминированное исследование пространства решений - это и есть симуляция НМТ.
Язык L распознаётся 3-ленточной МТ. Что из этого следует?
Ключевые идеи
- **k-ленточная МТ** симулируется однолепточной за O(t²). Удобнее для программирования, не мощнее по вычислимости
- **НМТ** принимает если хотя бы одна ветвь принимает. Симулируется детерминированно за 2^O(t). Основа определения класса NP
- **МТ с оракулом** мощнее обычной МТ. Оракульные барьеры (Baker-Gill-Solovay) объясняют трудность P vs NP - нужны нерелятивизируемые методы
- **Все варианты эквивалентны по вычислимости** - признают те же языки. Различия только в сложности симуляции
Связанные темы
Варианты МТ - основа теории сложности:
- P vs NP — NP определяется через НМТ за poly(n) шагов - вопрос в эффективности детерминированной симуляции
- Тезис Чёрча-Тьюринга — Эквивалентность всех разумных моделей вычислений - обобщение эквивалентности вариантов МТ
- Пространственная сложность — PSPACE определяется через МТ с ограничением по памяти, аналогично временным ограничениям
Вопросы для размышления
- GPU выполняет тысячи потоков параллельно. В чём принципиальное отличие параллельных вычислений от недетерминизма МТ?
- Квантовые компьютеры суперпозиционируют ветви вычисления. Означает ли это, что квантовый компьютер - это физическая реализация НМТ?
- Почему оракульный барьер (Baker-Gill-Solovay) не является доказательством P ≠ NP, хотя интуитивно кажется, что должен?