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,\Gamma ,\delta ,q_{0},g)$ onde

• $Q$ é o conjunto finito de estados
• $\Gamma$ é o alfabeto de fita
• $\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \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\rightarrow \{\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 ${\rm {ATIME}}(t(n))$, e uma linguagem decidida em espaço $c\cdot s(n)$ está na classe ${\rm {ASPACE}}(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:

• ${\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})$ são as linguagens decidíveis em tempo polinomial
• ${\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})$ são as linguagens decidíveis em espaço polinomial
• ${\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(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}{\rm {DTIME}}(2^{cf(n)})={\rm {DTIME}}(2^{O(f(n))})$
• $ATIME(g(n))\subseteq {\rm {DSPACE}}(g(n))$
• $NSPACE(g(n))\subseteq \bigcup _{c>0}{\rm {ATIME}}(c\times g(n)^{2})$

Quando $f(n)\geq \log(n)$ e $g(n)\geq \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.)

${\rm {ATIME}}(C,j)=\Sigma _{j}{\rm {TIME}}(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 ${\rm {TIME}}(C)$.

${\rm {coATIME}}(C,j)=\Pi _{j}{\rm {TIME}}(C)$ é a mesma classe, mas começando com um estado universal, é o complemento da linguagem de ${\rm {ATIME}}(f,j)$.

${\rm {ASPACE}}(C,j)=\Sigma _{\rm {SPACE}}(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\geq 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 ${\rm {SPACE}}(f)$ pro primeira level quando $f=\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 $\Sigma _{k}{\rm {P}}$ (respectivamente, $\Pi _{k}{\rm {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.
• Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X  Section 10.3: Alternation, pp. 348–354.
• Michael Sipser (2006). Introduction to the Theory of Computation, 2nd ed. [S.l.]: PWS Publishing. ISBN 0-534-95097-3  Section 10.3: Alternation, pp. 380–386.
• Christos Papadimitriou (1993). Computational Complexity 1st edition ed. [S.l.]: Addison Wesley. ISBN 0-201-53082-1  Section 16.2: Alternation, pp. 399–401.