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

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

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

Определения

Неформальное описание

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

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

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

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

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

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

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

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

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

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

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

Пример

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

Такая машина решает квантифицированные булевы формулы во времени и пространстве . ${\displaystyle n^{2}}$ ${\displaystyle n}$

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

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

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

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

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

• ALOGSPACE = P
• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE
• ${\displaystyle {\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})}$
• ${\displaystyle {\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))}$
• ${\displaystyle {\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),}$

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

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

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

Определение

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

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

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

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

Пример

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

Сворачивание классов

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

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

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

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

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

Ссылки

1. Чандра, Ашок К.; Стокмейер, Ларри Дж. (1976). «Alternation». Proc. 17th IEEE Symp. on Foundations of Computer Science . Хьюстон, Техас. стр. 98–108. doi :10.1109/SFCS.1976.4.
2. Козен, Д. (1976). «О параллелизме в машинах Тьюринга». Труды 17-го симпозиума IEEE по основам компьютерной науки . Хьюстон, Техас. стр. 89–97. doi :10.1109/SFCS.1976.20. hdl : 1813/7056 .
3. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation" (PDF) . Journal of the ACM . 28 (1): 114–133. doi :10.1145/322234.322243. S2CID  238863413. Архивировано из оригинала (PDF) 12 апреля 2016 г.
4. Иммерман, Нил (1988). «Недетерминированное пространство замкнуто относительно дополнения» (PDF) . SIAM Journal on Computing . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . doi :10.1137/0217058. 
5. Козен, Декстер (2006). Теория вычислений . Спрингер-Верлаг . п. 58. ИСБН 9781846282973.

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

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