Máquina de Turing alternante

El concepto de una ATM fue establecido por Chandra y Stockmeyer en 1976 (ver referencias).entonces esa configuración se dice que es aceptante, y sise 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.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)., la cabeza está en el extremo izquierdo de la cinta y la cinta contiene w), y rechaza si la configuración inicial es rechazante.si al examinar las configuraciones en cualquier entrada de longitudpasos, es suficiente para etiquetar la configuración inicial como aceptante o rechazante.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.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 solo la ramificación existencial, lo resuelva eficientemente.Las siguientes clases de complejidad son útiles para definir para ATMs: {\ Rm AP} = \ bigcup_ {k> 0} {\ rm ATIME} (n ^ k) son los lenguajes decidibles en tiempo polinomial {\ Rm APSPACE} = \ bigcup_ {k> 0} {\ rm ASPACE} (n ^ k) 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.Una forma más general de estas relaciones se expresa en la teoría del cómputo paralelo.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.(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 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 {\ Rm ATIME}(f, j).{\ Rm ASPACE} (C, j) = \ Sigma_j {\ rm ESPACIO} (C) se define de manera similar para el cálculo del espacio limitado.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).[2]​ Como corolario, la jerarquía {\ rm SPACE} (f) se desploma a su primer nivel cuando f = \ Omega (\ log) es Space constructible.[cita requerida] 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 (respectivamente, \ Pi_k ^ p).