Máquina de Turing alternante

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Sistema combinacional Autómata finito Autómata con pila Máquina de Turing Teoría de autómatasTeoría de autómatas.svg
Acerca de esta imagen


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 la aceptación de cómputos que generaliza las reglas usadas en la definición de las clases de complejidad NP y co-NP. El concepto de una ATM fue establecido por Chandra y Stockmeyer en 1976 (ver referencias).

Descripción informal[editar]

La definición de NP usa el modo existencial de computación: Si cualquier elección lleva a un estado de aceptación, entonces la computación completa acepta. La definición de co-NP usa el modo universal de computación: sólo si todas las opciones llevan a un estado de aceptación, la computación completa acepta. Una máquina de Turing alternante (o para ser más precisos, la definición de la aceptación de tal 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 grupos: estados existenciales y estados universales. Un estado existencial está aceptando si alguna transición conduce a un estado de aceptación; un estado universal está aceptando si cada transición conduce a un estado de aceptación. (Por lo tanto un estado universal con transiciones acepta incondicionalmente, un estado existencial sin transiciones rechaza incondicionalmente). La máquina como un conjunto acepta si el estado inicial está aceptando.

Definición formal[editar]

Formalmente, una máquina de Turing alternante (de una cinta) es una 5 tupla donde

  • es el conjunto finito de estados
  • es el alfabeto finito de la cinta
  • es llamada la función de transición (L desplaza la cabeza a la izquierda y R desplaza la cabeza a la derecha)
  • es el estado inicial
  • especifica el tipo de cada estado

Si M es un estado con entonces esa configuración se dice que es aceptante, y si la configuración se dice que es rechazante. Una configuración con se dice que es aceptante si todas las configuraciones en un solo paso son aceptantes, y rechazante si alguna configuración accesible en un solo paso es rechazante. Una configuración con se dice que es aceptante cuando existe alguna configuración accesible en un solo paso que es aceptante y recrechazante cuando todas las configuraciones en un solo paso son rechazantes (este es el tipo de todos los estados en una NTM). Se dice que M acepta una cadena de entrada w si la configuración inicial de M es aceptante (el estado de M es , la cabeza está en el extremo izquierdo de la cinta y la cinta contiene w), y rechaza si la configuración inicial es rechazante.

Límites de los recursos[editar]

Cuando se decide si una configuración de una ATM está aceptando o rechazando usando la definición anterior, no es necesario examinar todas las configuraciones accesibles a partir de la configuración actual. En particular, una configuración existencial puede etiquetarse como aceptante si se encuentra cualquier configuración sucesora aceptante, y una configuración universal puede ser etiquetada como rechazante si se encuentra que cualquier configuración sucesora es rechazante.

Una ATM decide un lenguaje formal en el si al examinar las configuraciones en cualquier entrada de longitud sólo hasta a pasos, es suficiente para etiquetar la configuración inicial como aceptante o rechazante. Una ATM decide un lenguaje en el espacio si es suficiente examinar, desde la izquierda, las configuraciones que no modifican las celdas de la cinta, más allá de la celda .

Un lenguaje que es decidido por algunas ATM en 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 .

Ejemplo[editar]

Puede ser que el más simple de los problemas que una máquina alternante puede resolver es el problema de fórmula Booleana cuantificada, que es una generalización del Problema de satisfactibilidad booleana en el que cada variable puede ser delimitada por un cuantificador universal o existencial.

La máquina alternante se ramifica existencialmente para probar todos los valores posibles de una variable cuantificada y universalmente para probar todos los valores posibles de

una variable cuantificada universalmente,de izquierda a derecha según el orden en el que 

están enlazados. Después de decidir un valor para todas las variables cuantificadas, la máquina lo acepta si la fórmula booleana resultante se evalúa como verdadera y rechaza si se evalúa como falso. Así la máquina está aceptando si un valor puede ser sustituido por la variable cuantificada existencialmente que hace que el problema restante sea satisfactorio, y en una variable cuantificada universalmente la máquina acepta si cualquier valor puede ser sustituido y el problema restante es satisfactorio.

Dicha máquina describe formulas cuantizadas boolenas en tiempo and espacio .

El problema de satisfactibilidad booleano puede ser visto como el caso especial donde todas las variables están cuantificadas existencialmente, permitiendo que el no determinismo ordinario, que usa sólo la ramificación existencial, lo resuelva eficientemente.

Clases de complejidad y comparación con máquinas determinantes de Turing[editar]

Las siguientes clases de complejidad son ​​útiles para definir para ATMs:

{\ Rm AP} = \ bigcup_ {k> 0} {\ rm ATIME} (n ^ k) </ math> son los lenguajes decidibles en tiempo polinomial {\ Rm APSPACE} = \ bigcup_ {k> 0} {\ rm ASPACE} (n ^ k) </ math> son los lenguajes decidibles en el espacio polinomial {\ Rm AEXPTIME} = \ bigcup_ {k> 0} {\ rm ATIME} (2 ^ {n ^ k}) son los lenguajes decidibles en tiempo exponencial

Estos son similares a las definiciones de P, PSPACE, y EXPTIME, teniendo en cuenta los recursos utilizados por un ATM en lugar de una máquina determinista Turing. Chandra, Kozen, y Stockmeyer[1] demostraron los teoremas

AP = PSPACE

{\ Rm DTIME} (2 ^ {cf (n)}) = {\ rm DTIME} (2 ^ {O (*)} \ mathrm {ASPACE} F (n)}}) </ math> \ Mathbm {ATIME} (g (n)) \ subseteq {\ rm DSPACE} (g (n)) </ math> {\ Rm ATIME} (c \ times g (n) ^ 2), \ mathrm {NSPACE} (g (n)) \ subseteq \ bigcup_ {c} Cuando <math> f (n) \ ge \ log (n) <math> g (n) \ ge \ log (n) </ math>.

Una forma más general de estas relaciones se expresa en la teoría del cómputo paralelo

Límites de alternancia[editar]

Definición[editar]

Una máquina Turing alterna con alternancias k 'es una máquina 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 están divididos en conjuntos k.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 l i .)

(C) es la clase de la función en el tiempo f \ en C que comienza por el estado existencial Y alternando a lo sumo <-j-1 </ math> veces. Se llama el nivel j de la jerarquía.

(C) es la misma clase, pero a partir de un estado universal, es el complemento del lenguaje de <matemáticas > {\ Rm ATIME} (f, j) </ math>.

{\ Rm ASPACE} (C, j) = \ Sigma_j {\ rm ESPACIO} (C) se define de manera similar para el cálculo del espacio limitado

Ejemplo[editar]

Consideremos el problema de minimización de circuitos: dado un circuito que calcula una función booleana y un número n, determine si hay un circuito con un máximo de ' 'N' 'que calcula la misma función' 'f' '. Una máquina de Turing alterna, con una alternancia, comenzando en un estado existencial, puede resolver este problema en tiempo polinomial (adivinando un circuito B con a lo más n puertas, cambiando entonces a un estado universal, adivinando Una entrada, y comprobando que la salida de B en esa entrada coincide con la salida de A en esa entrada).

Clases de colapso[editar]

Se dice que una jerarquía colapsa al nivel j si todo lenguaje en el nivel k de la jerarquía está en su nivel j </ math> Matemáticas

Como corolario del teorema de Immerman-Szelepcsényi, la jerarquía del espacio logarítmico colapsa a su primer nivel. [Ref> {{cita publicación | first1 = Neil | last1 = Immerman | url = http://www.cs. Umass.edu/~immerman/pub/space.pdf|título=Nondeterministic espacio se cierra en complementación | publicación = SIAM Journal on Computing volumen = 17 Como corolario, la jerarquía {\ rm SPACE} (f) se desploma a su primer nivel cuando f = \ Omega (\ log) es Space constructible [cita requerida].

Casos especiales[editar]

Una máquina de Turing alterna en tiempo polinomial con alternancias k , comenzando en un estado existencial (respectivamente, universal) puede decidir todos los problemas en la clase \ Sigma_k ^ p </ math> (respectivamente, \ Pi_k ^ p </ math>). <Ref> Plantilla:Cite libro </ ref> Estas clases a veces se denotan \ Sigma_k \ rm {P} y \ Pi_k \ rm {P} </ math>, respectivamente. Consulte el artículo jerarquía polinomial para obtener más detalles.

Otro caso especial de jerarquías de tiempo es la [[LH (complejidad)] jerarquía logarítmica]].

Referencias[editar]

  • Chandra, A.K., y Stockmeyer, L.J, 'Alternation', Proc. 17ª IEEE Symp. Sobre Foundations of Computer Science, Houston, Texas, 1976, pp. 98-108. Vea la siguiente entrada para la versión de diario.
  • Chandra, A.K. Y Kozen, D.C. y Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volumen 28, Número 1, págs. 114-133, 1981.
  • Michael Sipser. ISBN 0-534-94728-X.  Parámetro desconocido |Editorial= ignorado (se sugiere |editorial=) (ayuda); Parámetro desconocido |Año= ignorado (se sugiere |año=) (ayuda); Parámetro desconocido |Título= ignorado (se sugiere |título=) (ayuda); Falta el |título= (ayuda) Sección 10.3: Alternancia, pp. & Nbsp; 348 & gt; 354.
  • Michael Sipser. ISBN 0-534-95097-3.  Parámetro desconocido |Editorial= ignorado (se sugiere |editorial=) (ayuda); Parámetro desconocido |Año= ignorado (se sugiere |año=) (ayuda); Texto « Introducción a la Teoría de la Computación, 2ª ed. » ignorado (ayuda); Falta el |título= (ayuda) Sección 10.3: Alternancia, pp. & Nbsp; 380 & gt; 386.
  • Christos Papadimitriou. ISBN 0-201-53082-1.  Parámetro desconocido |Editorial= ignorado (se sugiere |editorial=) (ayuda); Parámetro desconocido |Edición= ignorado (se sugiere |edición=) (ayuda); Parámetro desconocido |Año= ignorado (se sugiere |año=) (ayuda); Texto « Complejo computacional » ignorado (ayuda); Falta el |título= (ayuda) Sección 16.2: Alternancia, pp. & Nbsp; 399 & gt; 401.

Véase también[editar]

  • Error en la cita: Etiqueta <ref> inválida; no se ha definido el contenido de las referencias llamadas alternation