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 un cajero automático fue establecido por Chandra y Stockmeyer [1] e independientemente por Kozen [2] en 1976, con una publicación conjunta en 1981. [3]
Definiciones
Descripción informal
La definición de NP utiliza el modo de cálculo existencial : 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: solo si todas las opciones conducen a un estado de aceptación, se acepta todo el cálculo. Una máquina de Turing alternante (o para ser más precisos, la definición de aceptación para 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 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 aceptable.
Definicion formal
Formalmente, una máquina de Turing alterna (una cinta) es una tupla de 5 dónde
- es el conjunto finito de estados
- es el alfabeto de cinta finito
- se llama función de transición ( L desplaza la cabeza hacia la izquierda y R desplaza la cabeza hacia la derecha)
- es el estado inicial
- especifica el tipo de cada estado
Si M está en un estado con entonces se dice que esa configuración está aceptando , y sise dice que la configuración está rechazando . Una configuración conse dice que acepta si todas las configuraciones alcanzables en un paso están aceptando, y rechaza si alguna configuración alcanzable en un paso es rechazada. Una configuración conse dice que acepta cuando existe alguna configuración accesible en un paso que acepta y rechaza cuando todas las configuraciones alcanzables en un paso son rechazadas (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 (el estado de M es, la cabeza está en el extremo izquierdo de la cinta, y la cinta contiene w ) está aceptando y rechazar si la configuración inicial es rechazada.
Tenga en cuenta que es imposible que una configuración acepte y rechace a la vez, sin embargo, algunas configuraciones pueden no aceptar ni rechazar, debido a la posibilidad de cálculos no terminales.
Límites de recursos
Al decidir si una configuración de un cajero automático está aceptando o rechazando 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 aceptable si se encuentra que cualquier configuración sucesora es aceptable, y una configuración universal puede etiquetarse como rechazada si se encuentra que cualquier configuración sucesora es rechazada.
Un cajero automático decide un idioma formal a tiemposi, en cualquier entrada de longitud n , examinar configuraciones sólo hastapasos es suficiente para etiquetar la configuración inicial como de aceptación o rechazo. Un cajero automático decide un idioma en el espacio si examina configuraciones que no modifican las celdas de cinta más allá del celda de la izquierda es suficiente.
Un idioma que se decide por algún cajero a tiempo por alguna constante se dice que está en la clase , y un idioma decidido en el espacio se dice que está en la clase .
Ejemplo
Quizás el problema más natural que deben resolver las máquinas alternas es el problema de la fórmula booleana cuantificada , que es una generalización del problema de satisfacibilidad booleano en el que cada variable puede estar limitada por un cuantificador existencial o universal. La máquina alterna 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 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 está aceptando si un valor puede ser sustituido por la variable que hace que el problema restante sea satisfactorio, y en una variable cuantificada universalmente, la máquina está aceptando si cualquier valor puede ser sustituido y el problema restante es satisfactorio.
Tal máquina decide fórmulas booleanas cuantificadas a tiempo y espacio .
El problema de satisfacibilidad booleano 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 solo ramificaciones existenciales, lo resuelva de manera eficiente.
Clases de complejidad y comparación con máquinas de Turing deterministas
Es útil definir las siguientes clases de complejidad para los cajeros automáticos:
- ¿Son las lenguas decidibles en tiempo polinomial?
- ¿Son los lenguajes decidibles en el espacio polinomial?
- ¿Son las lenguas 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
- ALOGESPACIO = P
- AP = PSPACE
- APSPACE = EXPTIME
- AEXPTIME = EXPSPACE
Cuándo y .
Una forma más general de estas relaciones se expresa en la tesis del cálculo paralelo .
Alternancia limitada
Definición
Una máquina de Turing alternante con k alternancias es una máquina de Turing alterna que cambia de un estado existencial a uno 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 conjunto i y un estado en el conjunto j < i .)
es la clase de idiomas decidible en el tiempo por una máquina que comienza en un estado existencial y alterna como máximo veces. Se llama el j- ésimo nivel del jerarquía.
se define de la misma manera, pero comenzando en un estado universal; Consiste en los complementos de los idiomas en.
se define de manera similar para el cálculo delimitado por el espacio.
Ejemplo
Considere el problema de minimización de circuitos : dado un circuito A que calcule una función booleana f y un número n , determine si hay un circuito con un máximo de n puertas que calcule 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 un máximo de 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 se colapsa al nivel j si todos los idiomas del nivelde la jerarquía está en su nivel j .
Como corolario del teorema de Immerman-Szelepcsényi , la jerarquía del espacio logarítmico colapsa a su primer nivel. [4] Como corolario, el La jerarquía colapsa a su primer nivel cuando es el espacio construible [ cita requerida ] .
Casos especiales
Una máquina de Turing alternante 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 indican y , respectivamente. Consulte el artículo sobre jerarquía de polinomios para obtener más detalles.
Otro caso especial de jerarquías de tiempo es la jerarquía logarítmica .
Referencias
- ↑ Chandra, Ashok K .; Stockmeyer, Larry J. (1976). "Alternancia". Proc. 17º IEEE Symp. sobre Fundamentos de la Informática . Houston, Texas. págs. 98-108. doi : 10.1109 / SFCS.1976.4 .
- ^ Kozen, D. (1976). "Sobre el paralelismo en las máquinas de Turing". Proc. 17º IEEE Symp. sobre Fundamentos de la Informática . Houston, Texas. págs. 89–97. doi : 10.1109 / SFCS.1976.20 . hdl : 1813/7056 .
- ^ a b 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 . Archivado desde el original (PDF) el 12 de abril de 2016.
- ^ Immerman, Neil (1988). "El espacio no determinista se cierra bajo complementación" (PDF) . Revista SIAM de Computación . 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.
Otras lecturas
- Michael Sipser (2006). Introducción a la Teoría de la Computación (2ª ed.). Publicación de 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 Nerode (2012). Teoría de los autómatas y sus aplicaciones . Springer Science & Business Media. ISBN 978-1-4612-0171-7.