Máquina de Turing alternante

Em teoria da complexidade, uma máquina de Turing alternante (MTA) é uma máquina de Turing não determinística (MTN) com uma regra para aceitar computações que generalizam as regras usadas nas definições de Classe de complexidade NP (complexidade) e Co-NP. O conceito de MTA foi estabelecido por Chandra and Stockmeyer, em 1976 (ver referências).

Definições

Descrição informal

A definição de NP usa o modo existencial de computação: se alguma escolha leva para um estado de aceitação, então toda a computação é aceita. A definição de co-NP usa o modo universal de computação: só se todas as escolhas levam para um estado de aceitação, então a computação é aceita. Uma máquina de Turing alternante alterna entre esses modos.

Uma máquina de Turing alternante é uma máquina de Turing não determinística que tem os estados divididos em dois grupos: estados existenciais e estados universais. Um estado existencial é aceito se alguma transição leva pra um estado de aceitação; um estado universal é aceito se toda transição leva para um estado de aceitação. A máquina como um todo aceita se o estado inicial é aceito.

Descrição formal

Formalmente, uma máquina de Turing alternante (de uma fita) é uma 5-Enupla $M=(Q,\mathrm{\Gamma },\delta ,q_0,g)$ onde

• $Q$ é o conjunto finito de estados
• $\mathrm{\Gamma }$ é o alfabeto de fita
• $\delta :Q\times \mathrm{\Gamma }\to 𝒫(Q\times \mathrm{\Gamma }\times \{L,R\})$ é a função de transição (L move a cabeça para a esquerda e R para a direita)
• $q_0\in Q$ é o estado inicial
• $g:Q\to \{\wedge ,\vee ,accept,reject\}$ especifica o tipo de cada estado

Se M esta num estado $q\in Q$ com $g(q)=accept$ então essa configuração é dita de aceitação, e se $g(q)=reject$ entao a configuração é dita de rejeição. A configuração com $g(q)=\wedge$ é dita de aceitação se todas as configurações levam em um estado de aceitação, e de rejeição se alguma configuração leva em um estado de rejeição. Uma configuração com $g(q)=\vee$ é dita de aceitação quando existe alguma configuração que leva em um estado de aceitação e de rejeição quando todas as configuração levam em um estado de rejeição. Diz-se que M aceita uma entrada w se a configuração inicial de M (o estado de M é $q_0$, a cabeça está no canto esquerdo da fita e a fita contém w) é de aceitação, e que M rejeita w se a configuração inicial é de rejeição.

Limite de recursos

Ao decidir se a configuração de uma MTA é de aceitação ou de rejeição usando a definição acima, não é necessário examinar todas as configurações que são alcançáveis a partir da configuração atual. Em particular, uma configuração existencial pode ser rotulada como de aceitação se alguma configuração seguinte é de aceitação, e uma configuração universal pode ser rotulada de rejeição se alguma configuração seguinte é de rejeição.

Uma MTA decide uma Linguagem formal em tempo $t(n)$ se, em cada entrada de tamanho $n$, examinando as configuração só acima de $t(n)$ passos é suficiente para rotular a configuração inicial como de aceitação ou de rejeição. Podemos dizer que uma MTA decide a linguagem em espaço $s(n)$ examinando se as configurações não modificam células da fita além de $s(n)$ células a partir da esquerda.

Uma linguagem que é decidida por alguma MTA em tempo $c\cdot t(n)$ por alguma constante $c>0$ está na classe $\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(t(n))$, e uma linguagem decidida em espaço $c\cdot s(n)$ está na classe $\mathrm{A}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))$.

Classes de complexidade e comparação com máquinas de Turing determinísticas

As Classe de complexidade são úteis para definir MTAs:

• $\mathrm{A}\mathrm{P}=\bigcup _{k>0}\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(n^k)$ são as linguagens decidíveis em tempo polinomial
• $\mathrm{A}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}=\bigcup _{k>0}\mathrm{A}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n^k)$ são as linguagens decidíveis em espaço polinomial
• $\mathrm{A}\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}=\bigcup _{k>0}\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(k^n)$ são as linguagens decidíveis em tempo exponencial

Estas definições são similares as de P (complexidade), PSPACE, e Exptime, considerando os recursos usados por uma MTA ao invéz de uma MTD. Chandra, Kozen, and Stockmeyer provaram esses teoremas:

• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE
• $ASPACE(f(n))=\bigcup _{c>0}\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{cf(n)})=\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{O(f(n))})$
• $ATIME(g(n))\subseteq \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g(n))$
• $NSPACE(g(n))\subseteq \bigcup _{c>0}\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(c\times g(n{)}^2)$

Quando $f(n)\ge \log (n)$ e $g(n)\ge \log (n)$ Isso é expresso pela Tese da computação paralela.

Alternância limitada

Definição

Uma máquina de Turing alternante com k alternações é uma máquina de Turing alternante que alterna de um estado existencial para um universal ou vice e versa mais de k+1 vezes. (Essa é uma máquina de Turing alternante que os estados são divididos em k grupos. Os estados nos grupos pares são universais e os estados nos grupos ímpares são existenciais (ou vice e versa). A máquina não tem transições entre estados no grupo i e no grupo j < i.)

$\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(C,j)={\mathrm{\Sigma }}_j\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(C)$ é a classe de função em tempo $f\in C$ começando com um estado existencial e alternando no máximo $j-1$ vezes. Esse é chamado o $j$-ésimo nível da hierarquia $\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(C)$.

$\mathrm{c}\mathrm{o}\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(C,j)={\mathrm{\Pi }}_j\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(C)$ é a mesma classe, mas começando com um estado universal, é o complemento da linguagem de $\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f,j)$.

$\mathrm{A}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(C,j)={\mathrm{\Sigma }}_{\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}}(C)$ é definido similarmente para cálculo de espaço delimitado.

Classes em colapso

É dito que o colapso hierárquico para o nível $j$ se toda linguagem no nível $k\ge j$ de uma hierarquia está no nível $j$.

Como o corolário de Immerman–Szelepcsényi theorem, o colapso da hierarquia de espaço logaritmântico para o primeira nível. Como o corolário o colapso da hierarquia $\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f)$ pro primeira level quando $f=\mathrm{\Omega }(\log )$ é uma Função construível

Classes especiais

Uma máquina de Turing alternante em tempo polinomial com k alternâncias, começando num estado existencial pode decidir todos os problemas na classe ${\mathrm{\Sigma }}_k\mathrm{P}$ (respectivamente, ${\mathrm{\Pi }}_k\mathrm{P}$).

Outro caso especial de hierarquia de tempo é logarithmic hierarchy.

Referências

• Chandra, A.K., and Stockmeyer, L.J, 'Alternation', Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas, 1976, pp. 98–108. See the next entry for the journal version.
• Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114–133, 1981.
• Predefinição:Citar livro Section 10.3: Alternation, pp. 348–354.
• Predefinição:Citar livro Section 10.3: Alternation, pp. 380–386.
• Predefinição:Citar livro Section 16.2: Alternation, pp. 399–401.