Введение

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

В теории вычислительной сложности, чередующаяся машина Тьюринга (ATM) — это недетерминированная машина Тьюринга (NTM) с правилом принятия вычислений, которое обобщает правила, используемые в определении классов сложности NP и co-NP. Концепция чередующейся машины Тьюринга была предложена Чандрой и Стокмейером и независимо Козеном в 1976 году, а совместная публикация результатов появилась в 1981 году.

Неофициальное описание

В определении NP используется экзистенциальный режим вычисления: если хотя бы один выбор приводит к принимающему состоянию, то всё вычисление принимается. В определении co NP используется универсальный режим вычисления: только если все выборы приводят к принимающему состоянию, всё вычисление принимается. Альтернирующая машина Тьюринга (или, точнее, определение принятия для такой машины) чередует эти режимы. Альтернирующая машина Тьюринга – это недетерминированная машина Тьюринга, состояния которой разделены на два множества: экзистенциальные состояния и универсальные состояния. Экзистенциальное состояние считается принимающим, если существует переход, ведущий к принимающему состоянию; универсальное состояние считается принимающим, если каждый переход ведёт к принимающему состоянию. (Таким образом, универсальное состояние без переходов принимает безусловно; экзистенциальное состояние без переходов отвергает безусловно). Машина в целом принимает, если начальное состояние является принимающим.

Ограничения ресурсов

При принятии решения о том, принимает или отклоняет ли конфигурация АТМ, используя вышеуказанное определение, не всегда необходимо исследовать все конфигурации, достижимые из текущей конфигурации. В частности, экзистенциальная конфигурация может быть помечена как принимающая, если хотя бы одна последующая конфигурация признана принимающей, а универсальная конфигурация может быть помечена как отклоняющая, если хотя бы одна последующая конфигурация признана отклоняющей. АТМ решает формальный язык за время *t*, если для любого входа длины *n* достаточно исследовать конфигурации только до *t* шагов, чтобы пометить начальную конфигурацию как принимающую или отклоняющую. АТМ решает язык в пространстве *s*, если достаточно исследовать конфигурации, которые не изменяют ячейки ленты за пределами *s*-й ячейки слева. Язык, который решается некоторым АТМ за время *t* для некоторой константы *t*, называется классом , а язык, решаемый в пространстве *s*, называется классом .

Пример

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

Особые случаи

Переключающаяся машина Тьюринга за полиномиальное время с k чередованиями, начиная в экзистенциальном (соответственно, универсальном) состоянии, может решить все задачи в классе (соответственно, ). Эти классы иногда обозначаются как и , соответственно. Подробности смотрите в статье о полиномиальной иерархии. Другим особым случаем иерархий по времени является логарифмическая иерархия.