Альтернативная машина Тьюринга

В теории сложности вычислений альтернативная машина Тьюринга ( АТМ ) — это недетерминированная машина Тьюринга ( НТМ ) с правилом принятия вычислений, обобщающим правила, используемые при определении классов сложности NP и co-NP . Идея банкомата была предложена Чандрой и Стокмейером. ^[1] и независимо от Козена ^[2] в 1976 году, с совместной публикацией в журнале в 1981 году. ^[3]

Определения

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

В определении NP используется экзистенциальный режим вычислений: если какой-либо выбор приводит к состоянию принятия, то все вычисление принимается. В определении co-NP используется универсальный режим вычислений: только если все варианты приводят к состоянию принятия, все вычисления принимаются. Попеременная машина Тьюринга (точнее, определение акцепта для такой машины) попеременно переключает эти режимы.

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

Формальное определение

Формально (одноленточная) альтернирующая машина Тьюринга представляет собой 5- кортеж $M=(Q,\Gamma ,\delta ,q_{0},g)$ где

$Q$ это конечное множество состояний
$\Gamma$ конечный ленточный алфавит
$\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$ называется функцией перехода ( L сдвигает голову влево, а R сдвигает голову вправо)
$q_{0}\in Q$ это начальное состояние
$g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}$ определяет тип каждого состояния

Если М находится в состоянии $q\in Q$ с $g(q)=accept$ тогда говорят, что эта конфигурация принимает , и если $g(q)=reject$ Говорят, что конфигурация отвергает . Конфигурация с $g(q)=\wedge$ Говорят, что принимают, если все конфигурации, достижимые за один шаг, принимают, и отклоняют, если какая-то конфигурация, достижимая за один шаг, является отклонением. Конфигурация с $g(q)=\vee$ Говорят, что принимается, когда существует некоторая конфигурация, достижимая за один шаг, которая принимается и отклоняется, когда все конфигурации, достижимые за один шаг, отвергаются (это тип всех состояний в классическом NTM, кроме конечного состояния). , Говорят, что M принимает входную строку если исходная конфигурация M (состояние M w $q_{0}$ , головка находится на левом конце ленты, и лента содержит w ) принимает и отклоняет, если исходная конфигурация отклоняет.

Обратите внимание, что конфигурация не может быть одновременно принимающей и отклоняющей, однако некоторые конфигурации могут быть ни принимающими, ни отклоняющими из-за возможности непрекращающихся вычислений.

Границы ресурсов

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

Банкомат определяет формальный язык вовремя $t(n)$ если на любом входе длины $n$ рассматривать конфигурации только до $t(n)$ шагов достаточно, чтобы пометить первоначальную конфигурацию как принимающую или отклоняющую. Банкомат определяет язык в космосе $s(n)$ при проверке конфигураций, которые не изменяют ячейки ленты за пределами $s(n)$ ячейки слева достаточно.

Язык, который определяется каким-то банкоматом во времени $c\cdot t(n)$ для некоторой константы $c>0$ говорят, что он в классе ${\mathsf {ATIME}}(t(n))$ и язык, решаемый в пространстве $c\cdot s(n)$ говорят, что он в классе ${\mathsf {ASPACE}}(s(n))$ .

Пример

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

Такая машина решает количественные логические формулы во времени. $n^{2}$ и космос $n$ .

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

Классы сложности и сравнение с детерминированными машинами Тьюринга

следующие классы сложности Для банкоматов полезно определить :

${\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})$ разрешимы ли языки за полиномиальное время?
${\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})$ являются ли языки разрешимыми в полиномиальном пространстве
${\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})$ разрешимы ли языки за экспоненциальное время?

Они аналогичны определениям P , PSPACE и EXPTIME , учитывая ресурсы, используемые банкоматом, а не детерминированной машиной Тьюринга. Чандра, Козен и Стокмейер ^[3] доказал теоремы

АЛОПРОСТРАНСТВО = P
АП = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE
${\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})$
${\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))$
${\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),$

когда $f(n)\geq \log(n)$ и $g(n)\geq \log(n)$ .

Более общая форма этих отношений выражается тезисом о параллельных вычислениях .

Ограниченное чередование

Определение

Попеременная машина Тьюринга с k альтернативами — это попеременная машина Тьюринга, которая переключается из экзистенциального состояния в универсальное или наоборот не более k −1 раз. (Это попеременная машина Тьюринга, состояния которой разделены на k наборов. Состояния в наборах с четными номерами являются универсальными, а состояния в наборах с нечетными номерами являются экзистенциальными (или наоборот). У машины нет переходов между состояниями в наборе. i и состояние в множестве j < i .)

${\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)$ класс языков, разрешимый во времени $f\in C$ машиной, начинающейся в экзистенциальном состоянии и чередующейся не более $j-1$ раз. Его называют $j-$ м уровнем ${\mathsf {TIME}}(C)$ иерархия.

${\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)$ определяется таким же образом, но начинается с универсального состояния; он состоит из дополнений языков в ${\mathsf {ATIME}}(f,j)$ .

${\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)$ определяется аналогично для вычислений, ограниченных пространством.

Пример

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

Свертывание классов

Говорят, что иерархия рушится до уровня $j,$ если каждый язык на уровне $k\geq j$ иерархии находится на уровне $j$ .

Как следствие теоремы Иммермана – Селепшени , иерархия логарифмического пространства схлопывается на свой первый уровень. ^[4] Как следствие ${\mathsf {SPACE}}(f)$ иерархия рушится на первый уровень, когда $f=\Omega (\log )$ можно ли построить пространство ^{[ нужна ссылка ]}.

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

Попеременная машина Тьюринга за полиномиальное время с k чередованиями, стартовавшая в экзистенциальном (соответственно универсальном) состоянии, может решить все задачи класса $\Sigma _{k}^{p}$ (соответственно, $\Pi _{k}^{p}$ ). ^[5]Эти классы иногда обозначаются $\Sigma _{k}{\rm {P}}$ и $\Pi _{k}{\rm {P}}$ , соответственно. смотрите в статье о полиномиальной иерархии Подробности .

Другим частным случаем временных иерархий является логарифмическая иерархия .

Ссылки

^ Чандра, Ашок К.; Стокмейер, Ларри Дж. (1976). «Чередование». Учеб. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. стр. 98–108. дои : 10.1109/SFCS.1976.4 .
^ Козен, Д. (1976). «О параллелизме в машинах Тьюринга». Учеб. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. стр. 89–97. дои : 10.1109/SFCS.1976.20 . hdl : 1813/7056 .
^ Перейти обратно: ^а ^б Чандра, Ашок К.; Козен, Декстер К.; Стокмейер, Ларри Дж. (1981). «Чередование» (PDF) . Журнал АКМ . 28 (1): 114–133. дои : 10.1145/322234.322243 . S2CID 238863413 . Архивировано из оригинала (PDF) 12 апреля 2016 г.
^ Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» (PDF) . SIAM Journal по вычислительной технике . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . дои : 10.1137/0217058 .
^ Козен, Декстер (2006). Теория вычислений . Спрингер Верлаг . стр. 58 . ISBN 9781846282973 .

Дальнейшее чтение

Майкл Сипсер (2006). Введение в теорию вычислений (2-е изд.). Издательство ПВС. ISBN 978-0-534-95097-2 . Раздел 10.3: Чередование, стр. 380–386.
Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 978-0-201-53082-7 . Раздел 16.2: Чередование, стр. 399–401.
Бахадыр Хусаинов; Анил Нероде (2012). Теория автоматов и ее приложения . Springer Science & Business Media. ISBN 978-1-4612-0171-7 .

[chasto-1] Чандра, Ашок К.; Стокмейер, Ларри Дж. (1976). «Чередование». Учеб. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. стр. 98–108. дои : 10.1109/SFCS.1976.4 .

[kozen-2] Козен, Д. (1976). «О параллелизме в машинах Тьюринга». Учеб. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. стр. 89–97. дои : 10.1109/SFCS.1976.20 . hdl : 1813/7056 .

[alternation-3] Перейти обратно: ^а ^б Чандра, Ашок К.; Козен, Декстер К.; Стокмейер, Ларри Дж. (1981). «Чередование» (PDF) . Журнал АКМ . 28 (1): 114–133. дои : 10.1145/322234.322243 . S2CID 238863413 . Архивировано из оригинала (PDF) 12 апреля 2016 г.

[4] Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» (PDF) . SIAM Journal по вычислительной технике . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . дои : 10.1137/0217058 .

[5] Козен, Декстер (2006). Теория вычислений . Спрингер Верлаг . стр. 58 . ISBN 9781846282973 .

[1]

[2]

[3]

[4]

[5]