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 onde
é o conjunto finito de estados é o alfabeto de fita é a função de transição (L move a cabeça para a esquerda e R para a direita) é o estado inicial especifica o tipo de cada estado
Se M esta num estado com então essa configuração é dita de aceitação, e se entao a configuração é dita de rejeição. A configuração com é 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 é 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 é , 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 se, em cada entrada de tamanho , examinando as configuração só acima de 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 examinando se as configurações não modificam células da fita além de células a partir da esquerda.
Uma linguagem que é decidida por alguma MTA em tempo por alguma constante está na classe , e uma linguagem decidida em espaço está na classe .
Classes de complexidade e comparação com máquinas de Turing determinísticas
As Classe de complexidade são úteis para definir MTAs:
são as linguagens decidíveis em tempo polinomial são as linguagens decidíveis em espaço polinomial 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
Quando e 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.)
é a classe de função em tempo começando com um estado existencial e alternando no máximo vezes. Esse é chamado o -ésimo nível da hierarquia .
é a mesma classe, mas começando com um estado universal, é o complemento da linguagem de .
é definido similarmente para cálculo de espaço delimitado.
Classes em colapso É dito que o colapso hierárquico para o nível se toda linguagem no nível de uma hierarquia está no nível .
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 pro primeira level quando é 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 (respectivamente, ).
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. Section 10.3: Alternation, pp. 348–354. Section 10.3: Alternation, pp. 380–386. Section 16.2: Alternation, pp. 399–401.
Categoria:Teoria da computação