Máquina de Turing alterna

Modelo de cálculo abstracto

En la teoría de la complejidad computacional , una máquina de Turing alterna ( ATM ) es una máquina de Turing no determinista ( NTM ) con una regla para aceptar cálculos que generaliza las reglas utilizadas en la definición de las clases de complejidad NP y co-NP . El concepto de cajero automático fue expuesto por Chandra y Stockmeyer ^[1] e independientemente por Kozen ^[2] en 1976, con una publicación conjunta en una revista en 1981. ^[3]

Definiciones

descripción informal

La definición de NP utiliza el modo existencial de cálculo: si alguna elección conduce a un estado de aceptación, entonces todo el cálculo acepta. La definición de co-NP utiliza el modo universal de cálculo: sólo si todas las opciones conducen a un estado de aceptación, todo el cálculo acepta. Una máquina de Turing alterna (o para ser más precisos, la definición de aceptación para dicha máquina) alterna entre estos modos.

Una máquina de Turing alterna es una máquina de Turing no determinista cuyos estados se dividen en dos conjuntos: estados existenciales y estados universales . Un estado existencial es de aceptación si alguna transición conduce a un estado de aceptación; un estado universal es de aceptación si cada transición conduce a un estado de aceptación. (Así, un estado universal sin transiciones acepta incondicionalmente; un estado existencial sin transiciones rechaza incondicionalmente). La máquina en su conjunto acepta si el estado inicial es de aceptación.

Definicion formal

Formalmente, una máquina de Turing alternante (de una cinta) es una tupla de 5 donde ${\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}$

• ${\displaystyle Q}$es el conjunto finito de estados
• ${\displaystyle \Gamma }$es el alfabeto de cinta finita
• ${\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}$se llama función de transición ( L desplaza la cabeza hacia la izquierda y R desplaza la cabeza hacia la derecha)
• ${\displaystyle q_{0}\in Q}$es el estado inicial
• ${\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}$especifica el tipo de cada estado

Si M está en un estado con entonces se dice que esa configuración se acepta , y si la configuración se dice que se rechaza . Se dice que una configuración con es aceptada si todas las configuraciones alcanzables en un paso son aceptadas y rechazada si alguna configuración alcanzable en un paso es rechazada. Se dice que una configuración con se acepta cuando existe alguna configuración alcanzable en un paso que se acepta y se rechaza cuando todas las configuraciones alcanzables en un paso se rechazan (este es el tipo de todos los estados en una NTM clásica excepto el estado final). Se dice que M acepta una cadena de entrada w si la configuración inicial de M (el estado de M es , el cabezal está en el extremo izquierdo de la cinta y la cinta contiene w ) es aceptable, y la rechaza si la configuración inicial es rechazando. ${\displaystyle q\in Q}$ ${\displaystyle g(q)=accept}$ ${\displaystyle g(q)=reject}$ ${\displaystyle g(q)=\wedge }$ ${\displaystyle g(q)=\vee }$ ${\displaystyle q_{0}}$

Tenga en cuenta que es imposible que una configuración acepte y rechace al mismo tiempo; sin embargo, algunas configuraciones pueden no aceptar ni rechazar, debido a la posibilidad de que los cálculos no terminen.

Límites de recursos

Al decidir si una configuración de un cajero automático se acepta o rechaza utilizando la definición anterior, no siempre es necesario examinar todas las configuraciones accesibles desde la configuración actual. En particular, una configuración existencial puede etiquetarse como aceptante si se encuentra que alguna configuración sucesora es aceptable, y una configuración universal puede etiquetarse como rechazante si se encuentra que alguna configuración sucesora es rechazante.

Un cajero automático decide un lenguaje formal a tiempo si, en cualquier entrada de longitud n , examinar las configuraciones solo hasta los pasos es suficiente para etiquetar la configuración inicial como aceptada o rechazada. Un cajero automático decide un idioma en el espacio si es suficiente examinar configuraciones que no modifican las celdas de la cinta más allá de la celda de la izquierda. ${\displaystyle t(n)}$ ${\displaystyle t(n)}$ ${\displaystyle s(n)}$ ${\displaystyle s(n)}$

Un idioma que se decide en algún cajero automático en el tiempo para alguna constante se dice que está en la clase , y un idioma decidido en el espacio se dice que está en la clase . ${\displaystyle c\cdot t(n)}$ ${\displaystyle c>0}$ ${\displaystyle {\mathsf {ATIME}}(t(n))}$ ${\displaystyle c\cdot s(n)}$ ${\displaystyle {\mathsf {ASPACE}}(s(n))}$

Ejemplo

Quizás el problema más natural que pueden resolver las máquinas alternas es el problema de fórmula booleana cuantificada , que es una generalización del problema de satisfacibilidad booleana en el que cada variable puede estar limitada por un cuantificador existencial o universal. La máquina alternante se bifurca existencialmente para probar todos los valores posibles de una variable cuantificada existencialmente y universalmente para probar todos los valores posibles de una variable cuantificada universalmente, en el orden de izquierda a derecha en el que están vinculados. Después de decidir un valor para todas las variables cuantificadas, la máquina acepta si la fórmula booleana resultante se evalúa como verdadera y rechaza si se evalúa como falsa. Así, en una variable cuantificada existencialmente, la máquina acepta si un valor puede sustituirse por la variable que hace que el problema restante sea satisfacible, y en una variable cuantificada universalmente, la máquina acepta si cualquier valor puede sustituirse y el problema restante es satisfacible.

Una máquina de este tipo decide fórmulas booleanas cuantificadas en el tiempo y el espacio . ${\displaystyle n^{2}}$ ${\displaystyle n}$

El problema booleano de satisfacibilidad puede verse como el caso especial en el que todas las variables se cuantifican existencialmente, lo que permite que el no determinismo ordinario, que utiliza sólo ramificaciones existenciales, lo resuelva eficientemente.

Clases de complejidad y comparación con las máquinas de Turing deterministas

Es útil definir las siguientes clases de complejidad para los cajeros automáticos:

• ${\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}$¿Son los lenguajes decidibles en tiempo polinomial?
• ${\displaystyle {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}$¿Son los lenguajes decidibles en el espacio polinomial?
• ${\displaystyle {\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})}$¿Son los idiomas decidibles en tiempo exponencial?

Son similares a las definiciones de P , PSPACE y EXPTIME , considerando los recursos utilizados por un cajero automático en lugar de una máquina de Turing determinista. Chandra, Kozen y Stockmeyer ^[3] demostraron los teoremas

• ESPACIOLOGICO = P
• AP = ESPACIO
• ESPACIO AP = TIEMPO EXP
• AEXPTIME = EXPESPACIO
• ${\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}),}$

cuándo y . ${\displaystyle f(n)\geq \log(n)}$ ${\displaystyle g(n)\geq \log(n)}$

Una forma más general de estas relaciones se expresa mediante la tesis del cálculo paralelo .

alternancia limitada

Definición

Una máquina de Turing alterna con k alternancias es una máquina de Turing alterna que cambia de un estado existencial a un estado universal o viceversa no más de k −1 veces. (Es una máquina de Turing alterna cuyos estados se dividen en k conjuntos. Los estados en conjuntos pares son universales y los estados en conjuntos impares son existenciales (o viceversa). La máquina no tiene transiciones entre un estado en un conjunto i y un estado en el conjunto j < i .)

${\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}$es la clase de lenguas decidibles en el tiempo por una máquina que comienza en un estado existencial y se alterna en la mayoría de los momentos. Se llama el j- ésimo nivel de la jerarquía. ${\displaystyle f\in C}$ ${\displaystyle j-1}$ ${\displaystyle {\mathsf {TIME}}(C)}$

${\displaystyle {\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)}$se define de la misma manera, pero comenzando en un estado universal; consta de los complementos de los idiomas en . ${\displaystyle {\mathsf {ATIME}}(f,j)}$

${\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)}$se define de manera similar para el cálculo acotado en el espacio.

Ejemplo

Considere el problema de minimización de circuitos : dado un circuito A que calcula una función booleana f y un número n , determine si hay un circuito con como máximo n puertas que calcula la misma función f . Una máquina de Turing alternante, con una alternancia, comenzando en un estado existencial, puede resolver este problema en tiempo polinómico (adivinando un circuito B con como máximo n puertas, luego cambiando a un estado universal, adivinando una entrada y verificando que la salida de B en esa entrada coincide con la salida de A en esa entrada).

Clases colapsadas

Se dice que una jerarquía colapsa al nivel j si cada idioma en el nivel de la jerarquía está en su nivel j . ${\displaystyle k\geq j}$

Como corolario del teorema de Immerman-Szelepcsényi , la jerarquía espacial logarítmica colapsa a su primer nivel. ^[4] Como corolario, la jerarquía colapsa a su primer nivel cuando el espacio es construible ^{[ cita necesaria ]} . ${\displaystyle {\mathsf {SPACE}}(f)}$ ${\displaystyle f=\Omega (\log )}$

Casos especiales

Una máquina de Turing alterna en tiempo polinomial con k alternancias, comenzando en un estado existencial (respectivamente, universal) puede decidir todos los problemas de la clase (respectivamente, ). ^[5] Estas clases a veces se denotan y , respectivamente. Consulte el artículo sobre jerarquía polinomial para obtener más detalles. ${\displaystyle \Sigma _{k}^{p}}$ ${\displaystyle \Pi _{k}^{p}}$ ${\displaystyle \Sigma _{k}{\rm {P}}}$ ${\displaystyle \Pi _{k}{\rm {P}}}$

Otro caso especial de jerarquías temporales es la jerarquía logarítmica .

Referencias

1. Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternancia". Proc. 17º Simposio IEEE. sobre Fundamentos de la Informática . Houston, Texas. págs. 98-108. doi :10.1109/SFCS.1976.4.
2. Kozen, D. (1976). "Sobre el paralelismo en las máquinas de Turing". Proc. 17º Simposio IEEE. sobre Fundamentos de la Informática . Houston, Texas. págs. 89–97. doi :10.1109/SFCS.1976.20. hdl : 1813/7056 .
3. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). «Alternancia» (PDF) . Revista de la ACM . 28 (1): 114-133. doi :10.1145/322234.322243. S2CID  238863413. Archivado desde el original (PDF) el 12 de abril de 2016.
4. Immerman, Neil (1988). "El espacio no determinista está cerrado bajo complementación" (PDF) . Revista SIAM de Computación . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . doi :10.1137/0217058. 
5. Kozen, Dexter (2006). Teoría de la Computación . Springer-Verlag . pag. 58.ISBN​ 9781846282973.

Otras lecturas

• Michael Sipser (2006). Introducción a la Teoría de la Computación (2ª ed.). Publicación PWS. ISBN 978-0-534-95097-2.Sección 10.3: Alternancia, págs. 380–386.
• Christos Papadimitriou (1993). Complejidad computacional (1ª ed.). Addison Wesley. ISBN 978-0-201-53082-7.Sección 16.2: Alternancia, págs. 399–401.
• Bakhadyr Khoussainov; Anil Nerodo (2012). Teoría de los autómatas y sus aplicaciones. Medios de ciencia y negocios de Springer. ISBN 978-1-4612-0171-7.