Saltar para o conteúdo

2-EXPTIME

Origem: Wikipédia, a enciclopédia livre.

Na teoria da Complexidade Computacional, a  classe de complexidade 2-EXPTIME (também chamada 2-EXP) é o conjunto de todos os problemas de decisão solucionáveis por uma Máquina de Turing Determinística em tempo O(22p(n)), onde p(n) é uma função polinomial de n.

Em termos de DTIME,

Nós sabemos que:

P NP PSPACE EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY.

2-EXPTIME também pode ser reformulado como a classe do espaço AEXPSPACE, os problemas que podem ser solucionados por uma Máquina de Turing Alternada em espaço exponencial. Esse é o único jeito para ver que EXPSPACE 2-EXPTIME, já que uma Máquina de Turing alternada é pelo menos tão poderosa quanto uma Máquina de Turing determinística.[1]

2-EXPTIME é uma classe em uma hierarquia de classes de complexidade com crescente limite de tempo. a classe 3-EXPTIME é definida similarmente a 2-EXPTIME mas com limite de tempo exponencial triplo . Isso pode ser generalizado para cada vez maiores limites de tempos.

Problemas 2-EXPTIME-completo

[editar | editar código-fonte]

Várias generalizações de jogos totalmente observáveis são EXPTIME-completo. Esses jogos podem ser vistos como instâncias particulares de uma classe de sistemas de transição definida em termos de um conjunto de variaveis de estado e ações/eventos que mudam os valores das variáveis de estado, juntamente com a pergunta da existência de uma estratégia vencedora.

A generalização dessa classe de problemas totalmente observáveis a parcialmente observáveis leva a complexidade de EXPTIME-completo para 2-EXPTIME-completo.[2]

  1. Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7.
  2. Jussi Rintanen (2004). «Complexity of Planning with Partial Observability» (PDF). AAAI Press. Proceedings of International Conference on Automated Planning and Scheduling: 345–354