Máquina de Turing alternada – Wikipédia, a enciclopédia livre

Em complexidade de computação teórica, uma máquina de Turing alternada (MTA) é uma máquina de Turing não-determinística (MTN) com a regra que aceita computações que generalizam regras usadas na definição da complexidade das classes NP e co-NP. O conceito de uma ATM foi criado por Chandra e Stockmeyer e independentemente por Kozen em 1976 (veja as referências).

Definições[editar | editar código-fonte]

Descrição Informal[editar | editar código-fonte]

A definição de NP usa o modo existencial da computação: se alguma escolha leva a um estado de aceitação, então toda a computação é aceita. A definição de co-NP usa o modo universal da computação: apenas se todas as escolhas levam a um estado de aceitação, então toda a computação é aceita. Uma máquina de Turing alternativa (ou para ser mais preciso, a definição de aceitação para cada máquina) altera entre esses dois modos.

Uma alternating Turing machine é uma máquina de Turing não-determinística onde seus estados são divididos entre dois tipos: estados existenciais e estado universais. Um estado existencial aceita se alguma transação leva para um estado de aceitação; um estado universal aceita se todas as transações levam para um estado de aceitação. (Assim um estado universal sem transações aceita incondicionalmente; um estado existencial sem transações rejeita incondicionalmente. A máquina como um todo, aceita se o estado inicial é de aceitação.

Definição formal[editar | editar código-fonte]

Formalmente, uma máquina de Turing alternada é uma 5-tupla ${\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}$ onde

• ${\displaystyle Q}$ é uma quantidade finita de estados
• ${\displaystyle \Gamma }$ é um alfabeto finito
• ${\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}$ é chamado de transação de função (L avança a cabeça para a esquerda e R avança a cabeça para direita.
• ${\displaystyle q_{0}\in Q}$ é o estado inicial
• ${\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}$ especifica o tipo de cada estado

Se M é um estado ${\displaystyle q\in Q}$ com ${\displaystyle g(q)=aceita}$ então essa é uma configuração de aceitação e se ${\displaystyle g(q)=rejeita}$ então será uma configuração de rejeição. A configuração com ${\displaystyle g(q)=\wedge }$ é dita de aceitação se todas as configurações alcançáveis em um passo são de aceitação, e é dita de rejeição se alguma configuração alcancável em um único passo é de rejeição. A configuração com ${\displaystyle g(q)=\vee }$ é dita de aceitação quando existe alguma configuração alcançável em um único passo de aceitação, e é de rejeição quando todas as configuração alcançáveis em um único passo são de rejeição. M irá aceitar uma string de entrada w se a configuração inicial de M (o estado de M é ${\displaystyle q_{0}}$, a cabeça da fita está na extremidade esquerda da fita e a fita contém a palavra w)

Limite de recursos[editar | editar código-fonte]

Quando está se decidindo 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 alcançáveis a partir da configuração atual. Particularmente, uma configuração existencial pode ser rotulada de aceitação se algum configuração sucessora é de aceitação e uma configuração universal pode ser rotuladas de rejeição se alguma configuração sucessora é de rejeição.

Uma MTA decide uma linguagem formal em tempo ${\displaystyle t(n)}$ se, para qualquer entrada de tamanho ${\displaystyle n}$, examinando configurações de ${\displaystyle t(n)}$ passos é suficiente para saber se a configuração inicial é de aceitação ou de rejeição. Um MTA decide linguagens em espaço ${\displaystyle s(n)}$ se examinando configurações onde elas não modificam a fita além de ${\displaystyle s(n)}$ célula à partir da extremidade esquerda.

Uma linguagem que é decidida por algum MTA em tempo ${\displaystyle c\cdot t(n)}$ para algumas constantes ${\displaystyle c>0}$ é dita que faz parte da classe ${\displaystyle {\rm {ATIME}}(t(n))}$ e uma linguagem que é decidida em espaço ${\displaystyle c\cdot s(n)}$ é dita que faz parte da classe ${\displaystyle {\rm {ASPACE}}(s(n))}$.

Exemplos[editar | editar código-fonte]

Talvez o problema mais simples de se resolver para máquinas alternadas seja o problema de fórmula booleana totalmente quantificada, que é uma generalização do problema de Satisfatibilidade booleana em que cada variável pode ser relacionada por um quantificador universal ou existencial. Os ramos existenciais da máquina alternada tenta todas as possíveis valorações dos quantificadores existenciais e todos as valorações possíveis para os quantificadores universais, em ordem, da esquerda para direita. Depois de decidir os valores para todos as variáveis quantificadas, a máquina aceita ou rejeita de acordo com o resultado booleano da fórmula, resultando em verdadeiro ou falso. Assim nas variáveis existenciais quantificadas a máquina aceita se seu valor pode ser substituído por uma variável que torna o problema satisfatível e nas variáveis universais quantificadas a máquina aceita se qualquer valor possa ser substituído tornando o problema satisfatível.

Tal máquina decide fórmulas booleanas quantificadas em tempo ${\displaystyle n^{2}}$ e espaço ${\displaystyle n}$.

O problema booleano da satisfatibilidade pode ser visto como o caso especial onde todas as variáveis são quantificadores existenciais, usando apenas o ramo existencial, resolvendo-o mais eficientemente.

Complexidade das classes e comparação com Máquinas de Turing determinísticas[editar | editar código-fonte]

As classes de complexidade são usadas para definir MTAs:

• ${\displaystyle {\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})}$ são linguagens decididas em tempo polinomial
• ${\displaystyle {\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})}$ são as linguagens decididas em espaço polinomial
• ${\displaystyle {\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})}$ são as linguagens decididas em tempo exponencial

Elas são parecidas na definição de P, PSPACE, and Exptime, considerando que os recursos usados por uma MTA são parecidos com os das máquinas de Turing determinísticas.

• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE
• ${\displaystyle \mathrm {ASPACE} (f(n))=\bigcup _{c>0}{\rm {DTIME}}(2^{cf(n)})={\rm {DTIME}}(2^{O(f(n))})}$
• ${\displaystyle \mathrm {ATIME} (g(n))\subseteq {\rm {DSPACE}}(g(n))}$
• ${\displaystyle \mathrm {NSPACE} (g(n))\subseteq \bigcup _{c>0}{\rm {ATIME}}(c\times g(n)^{2})}$

When ${\displaystyle f(n)\geq \log(n)}$ and ${\displaystyle g(n)\geq \log(n)}$ Essa é expressada por Tese da computação paralela.

Alternação limitada[editar | editar código-fonte]

Definição[editar | editar código-fonte]

Uma alternating Turing machine with k alternations é uma máquina de Turing alternada com trocas de um estado existencial para um estado universal ou vice-versa por não mais que k-1 vezes. (É uma máquina de Turing alternada onde os estados são divididos em k conjuntos. Os estados pares são universais e os ímpares são existenciais (ou vice-versa). A máquina não tem transições entre estados do conjunto i para um estado j < i.)

${\displaystyle {\rm {ATIME}}(C,j)=\Sigma _{j}{\rm {TIME}}(C)}$ é a classe das funções em tempo ${\displaystyle f\in C}$ começando por um estado existencial e alternando por no máximo ${\displaystyle j-1}$ vezes. Ela é chamada de ${\displaystyle j}$th level da hierarquia ${\displaystyle {\rm {TIME}}(C)}$.

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

${\displaystyle {\rm {ASPACE}}(C,j)=\Sigma _{\rm {SPACE}}(C)}$ é definida similarmente para espaços limitados.

Exemplo[editar | editar código-fonte]

Considerando a Minimização de circuitos: tendo um circuito A computando uma Função booleana f e um número n determine se aquele circuito com no máximo n portas computa a mesma função f. Uma máquina de Turing alternada, com uma alternação, partindo de um estado existencial pode resolver esse problema em tempo polinomial (supondo um circuito B com no máximo n portas, então alternando para um estado universal, supondo uma entrada e checando que a saída de B pra aquela entrada coincide com a saída de A com aquela entrada).

"Collapsing classes"[editar | editar código-fonte]

Se diz que temos uma hierarquia em colapso de level ${\displaystyle j}$ se toda linguagem no level ${\displaystyle k\geq j}$ de uma hierarquia está dentro do level ${\displaystyle j}$.

Casos especiais[editar | editar código-fonte]

Uma máquina de Turing alternada de tempo polinomial com k alterações, começando por um estado existencial (respectivamente, universal) pode decidir todos os problemas que estão na classe ${\displaystyle \Sigma _{k}^{p}}$ (respectivamente, ${\displaystyle \Pi _{k}^{p}}$).^[1] Essas classes as vezes são denotadas por ${\displaystyle \Sigma _{k}{\rm {P}}}$ and ${\displaystyle \Pi _{k}{\rm {P}}}$, respectivamente.

Outro caso especial de tempos hierárquicos é o logarithmic hierarchy.

Referências

Bibliografia[editar | editar código-fonte]

• 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 third entry for the journal version.
• Kozen, D.C., 'On parallelism in Turing machines', Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas, 1976, pp. 89–97. 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.