Máquina de Turing alterna

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 computaciones que generaliza las reglas utilizadas en la definición de las clases de complejidad NP y co-NP . El concepto de ATM fue presentado 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 de computación existencial : si alguna elección conduce a un estado de aceptación, entonces toda la computación acepta. La definición de co-NP utiliza el modo de computación universal : solo si todas las elecciones conducen a un estado de aceptación, toda la computación acepta. Una máquina de Turing alternante (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 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 conduce a un estado de aceptación; un estado universal es de aceptación si todas las transiciones conducen 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 alternante (de una cinta) es una 5- tupla. $M=(Q,\Gamma ,\delta ,q_{0},g)$ dónde

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

Si M está en un estado $q\in Q$ con $g(q)=accept$ entonces se dice que esa configuración es aceptable , y si $g(q)=reject$ Se dice que la configuración está rechazando . Una configuración con $g(q)=\wedge$ Se dice que es aceptable si todas las configuraciones alcanzables en un paso son aceptables, y rechaza si alguna configuración alcanzable en un paso es rechazable. Una configuración con $g(q)=\vee$ Se dice que acepta cuando existe alguna configuración alcanzable en un paso que acepta y rechaza cuando todas las configuraciones alcanzables en un paso 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 $q_{0}$ , el cabezal está en el extremo izquierdo de la cinta, y la cinta contiene w ) es aceptando, y rechazar si la configuración inicial es rechazando.

Tenga en cuenta que es imposible que una configuración sea a la vez de aceptación y de rechazo; sin embargo, algunas configuraciones pueden no ser ni de aceptación ni de rechazo, debido a la posibilidad de cálculos que no terminan.

límites de recursos

Al determinar si una configuración de un cajero automático es de aceptación o rechazo según la definición anterior, no siempre es necesario examinar todas las configuraciones alcanzables desde la configuración actual. En particular, una configuración existencial puede etiquetarse como de aceptación si se encuentra que alguna configuración sucesora es de aceptación, y una configuración universal puede etiquetarse como de rechazo si se encuentra que alguna configuración sucesora es de rechazo.

Un cajero automático decide un lenguaje formal en el tiempo $t(n)$ si, en cualquier entrada de longitud $n$ , se examinan configuraciones solo hasta $t(n)$ Los pasos son suficientes para etiquetar la configuración inicial como de aceptación o rechazo. Un cajero automático decide un idioma en el espacio $s(n)$ si se examinan configuraciones que no modifican las celdas de cinta más allá de la $s(n)$ La celda de la izquierda es suficiente.

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

Ejemplo

Quizás el problema más natural para que lo resuelvan las máquinas alternantes sea 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 que están limitadas. 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 se puede sustituir un valor por la variable que haga 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.

Dicha máquina decide fórmulas booleanas cuantificadas en el tiempo $n^{2}$ y espacio $n$ .

El problema de satisfacibilidad booleana puede considerarse como un caso especial en el que todas las variables están cuantificadas existencialmente, lo que permite que el no determinismo ordinario, que utiliza únicamente 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 en los cajeros automáticos:

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

Estas 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 que, para todo $f(n)\geq \log(n)$ y $g(n)\geq \log(n)$ :

${\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}),$

En particular:

ESPACIO DE REGISTRO = P
AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE

Una forma más general de estas relaciones se expresa mediante la tesis de la computación paralela .

Alternancia limitada

Definición

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

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

${\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 las lenguas en ${\mathsf {ATIME}}(f,j)$ .

${\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)$ Se define de forma similar para la computación con límites espaciales.

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 , determinar si existe un circuito con como máximo n compuertas que calcule 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 polinomial (adivinando un circuito B con como máximo n compuertas, luego cambiando a un estado universal, adivinando una entrada y comprobando que la salida de B para esa entrada coincide con la salida de A para esa entrada).

Clases en colapso

Se dice que una jerarquía se derrumba al nivel $j$ si cada lenguaje en el nivel $k\geq j$ de la jerarquía está en su nivel $j$ .

Como corolario del teorema de Immerman-Szelepcsényi , la jerarquía del espacio logarítmico se reduce a su primer nivel. ^{[ 4 ]} Como corolario, ${\mathsf {SPACE}}(f)$ La jerarquía se derrumba hasta su primer nivel cuando $f=\Omega (\log )$ ¿Es construible el espacio ?

Casos especiales

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

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

Referencias

↑ Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation". Proc. 17th IEEE Symp. on Foundations of Computer Science . Houston, Texas. pp. 98– 108. doi : 10.1109/SFCS.1976.4 .
↑ Kozen, D. (1976). "Sobre el paralelismo en las máquinas de Turing". Actas del 17.º Simposio IEEE sobre Fundamentos de la Informática . Houston, Texas. pp. 89–97 . doi : 10.1109/SFCS.1976.20 . hdl : 1813/7056 .
1 2 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. Archivado del original (PDF) el 12 de abril de 2016.
↑ Immerman, Neil (1988). "El espacio no determinista es cerrado bajo complementación" (PDF) . SIAM Journal on Computing . 17 (5): 935– 938. CiteSeerX 10.1.1.54.5941 . doi : 10.1137/0217058 .
^ Kozen, Dexter (2006). Teoría de la Computación . Springer-Verlag . pag. 58 . ISBN 9781846282973.

Lecturas adicionales

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.
Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990), "Alternancia" , en Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (eds.), Complejidad estructural II , Berlín, Heidelberg: Springer, págs. 63–96 , doi : 10.1007/978-3-642-75357-2_4 , ISBN 978-3-642-75357-2, consultado el 19 de mayo de 2025
Bakhadyr Khoussainov; Anil Nerode (2012). Teoría de autómatas y sus aplicaciones . Springer Science & Business Media. ISBN 978-1-4612-0171-7.

[chasto-1] Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation". Proc. 17th IEEE Symp. on Foundations of Computer Science . Houston, Texas. pp. 98– 108. doi : 10.1109/SFCS.1976.4 .

[kozen-2] Kozen, D. (1976). "Sobre el paralelismo en las máquinas de Turing". Actas del 17.º Simposio IEEE sobre Fundamentos de la Informática . Houston, Texas. pp. 89–97 . doi : 10.1109/SFCS.1976.20 . hdl : 1813/7056 .

[alternation-3] 1 2 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. Archivado del original (PDF) el 12 de abril de 2016.

[4] Immerman, Neil (1988). "El espacio no determinista es cerrado bajo complementación" (PDF) . SIAM Journal on Computing . 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.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]