Máquina de Turing alternada

Modelo computacional abstracto

En la teoría de la complejidad computacional , una máquina de Turing alternante ( 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 ATM fue establecido 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 computación: si cualquier elección lleva a un estado de aceptación, entonces todo el cómputo acepta. La definición de co-NP utiliza el modo universal de computación: solo si todas las elecciones llevan a un estado de aceptación, todo el cómputo acepta. Una máquina de Turing alternante (o para ser más precisos, la definición de aceptación para una máquina de este tipo) alterna entre estos modos.

Una máquina de Turing alternante 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 lleva a un estado de aceptación; un estado universal es de aceptación si cada transición lleva a un estado de aceptación. (Por lo tanto, 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.

Definición formal

Formalmente, una máquina de Turing alternada (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 está aceptando , y si la configuración está rechazando . Se dice que una configuración con está aceptando si todas las configuraciones alcanzables en un paso están aceptando, y rechazando si alguna configuración alcanzable en un paso está rechazando. Se dice que una configuración con está aceptando cuando existe alguna configuración alcanzable en un paso que está aceptando y rechazando cuando todas las configuraciones alcanzables en un paso están rechazando (este es el tipo de todos los estados en un NTM clásico 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 , la cabeza está en el extremo izquierdo de la cinta y la cinta contiene w ) está aceptando, y que rechaza si la configuración inicial está 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 sea a la vez de aceptación y rechazo; sin embargo, algunas configuraciones pueden no ser ni de aceptación ni de rechazo, debido a la posibilidad de cálculos no terminantes.

Límites de recursos

Al decidir si una configuración de un cajero automático es de aceptación o de rechazo utilizando la definición anterior, no siempre es necesario examinar todas las configuraciones alcanzables a partir de la configuración actual. En particular, una configuración existencial puede etiquetarse como de aceptación si se descubre que alguna configuración sucesora la acepta, y una configuración universal puede etiquetarse como de rechazo si se descubre que alguna configuración sucesora la rechaza.

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

Un lenguaje que es decidido por algún ATM en el tiempo para alguna constante se dice que está en la clase , y un lenguaje 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

Tal vez el problema más natural para que las máquinas alternantes lo resuelvan es el problema de la 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 ramifica 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 limitados. 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. Por lo tanto, en una variable cuantificada existencialmente, la máquina acepta si se puede sustituir un valor por la variable que hace que el problema restante sea satisfacible, y en una variable cuantificada universalmente, la máquina acepta si se puede sustituir cualquier valor y el problema restante es satisfacible.

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

El problema de satisfacibilidad booleana puede verse como el caso especial en el que todas las variables están cuantificadas existencialmente, lo que permite que el no determinismo ordinario, que utiliza solo ramificaciones existenciales, lo resuelva de manera eficiente.

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

Las siguientes clases de complejidad son útiles para definir para los cajeros automáticos:

• ${\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}$¿Son los idiomas decidibles en tiempo polinomial?
• ${\displaystyle {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}$¿Son los idiomas 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

• ESPACIO ALOGICO = P
• AP = ESPACIO P
• APSPACE = TIEMPO EXP
• 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}),}$

cuando 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 de la computación paralela .

Alternancia acotada

Definición

Una máquina de Turing alternada con k alternancias es una máquina de Turing alternada 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 alternada 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 el conjunto i y un estado en el conjunto j < i .)

${\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}$es la clase de lenguajes decidibles en el tiempo por una máquina que comienza en un estado existencial y se alterna en la mayoría de los casos. Se denomina nivel j 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; consiste en 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 limitado en el espacio.

Ejemplo

Consideremos 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 calcule la misma función f . Una máquina de Turing alternada, con una alternancia, comenzando en un estado existencial, puede resolver este problema en tiempo polinomial (suponiendo un circuito B con como máximo n puertas, luego cambiando a un estado universal, suponiendo una entrada y verificando que la salida de B en esa entrada coincida 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 del espacio logarítmico colapsa a su primer nivel. ^[4] Como corolario, la jerarquía colapsa a su primer nivel cuando el espacio es construible ^{[ cita requerida ]} . ${\displaystyle {\mathsf {SPACE}}(f)}$ ${\displaystyle f=\Omega (\log )}$

Casos especiales

Una máquina de Turing alternada en tiempo polinomial con k alternancias, comenzando en un estado existencial (respectivamente, universal) puede resolver todos los problemas de la clase (respectivamente, ). ^[5] Estas clases a veces se denotan como 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". Actas del 17.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación . 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. 17th IEEE Symp. on Foundations of Computer Science . 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.

Lectura adicional

• Michael Sipser (2006). Introducción a la teoría de la computación (2.ª ed.). PWS Publishing. 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 Nerode (2012). Teoría de autómatas y sus aplicaciones. Springer Science & Business Media. ISBN 978-1-4612-0171-7.