Máquina de Turing alternada

máquina de Turing não-determinística

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

Descrição Informal

editar

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

Formalmente, uma máquina de Turing alternada é uma 5-tupla   onde

  •   é uma quantidade finita de estados
  •   é um alfabeto finito
  •   é 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.
  •   é o estado inicial
  •   especifica o tipo de cada estado

Se M é um estado   com   então essa é uma configuração de aceitação e se   então será uma configuração de rejeição. A configuração com   é 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   é 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 é  , a cabeça da fita está na extremidade esquerda da fita e a fita contém a palavra w)

Limite de recursos

editar

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   se, para qualquer entrada de tamanho  , examinando configurações de   passos é suficiente para saber se a configuração inicial é de aceitação ou de rejeição. Um MTA decide linguagens em espaço   se examinando configurações onde elas não modificam a fita além de   célula à partir da extremidade esquerda.

Uma linguagem que é decidida por algum MTA em tempo   para algumas constantes   é dita que faz parte da classe   e uma linguagem que é decidida em espaço   é dita que faz parte da classe  .


Exemplos

editar

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   e espaço  .

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

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

  •   são linguagens decididas em tempo polinomial
  •   são as linguagens decididas em espaço polinomial
  •   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
  •  
  •  
  •  

When   and   Essa é expressada por Tese da computação paralela.

Alternação limitada

editar

Definição

editar

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.)

  é a classe das funções em tempo   começando por um estado existencial e alternando por no máximo   vezes. Ela é chamada de  th level da hierarquia  .

  é a mesma classe, mas ela começa por um estado universal e é o complemento da linguagem  .

  é definida similarmente para espaços limitados.

Exemplo

editar

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

Se diz que temos uma hierarquia em colapso de level   se toda linguagem no level   de uma hierarquia está dentro do level  .

Casos especiais

editar

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   (respectivamente,  ).[1] Essas classes as vezes são denotadas por   and  , respectivamente.

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

Referências

  1. Kozen, Dexter (2006). Theory of Computation. [S.l.]: Springer-Verlag. p. 58. ISBN 9781846282973 

Bibliografia

editar