EXPSPACE

Em teoria da complexidade computacionais, EXPSPACE é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em espaço O(2^p(n)) onde p(n) é uma função polinomial de n. (Alguns autores restringem p(n) para uma função linear, mas a maioria chama a classe resultante de ESPACE.) Se, por outro lado, nós usamos uma máquina não determinísitica, teremos a classe NEXPSPACE, que é igual a EXPSPACE pelo teorema de savitch.

Em termos de DSPACE e NSPACE, temos que

${\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})$

Um problema de decisão é EXPSPACE-completo se este está em EXPSPACE, e para todo problema em EXPSPACE existe uma reduçao polinomial para este dado problema. Em outras palavras, existe um algoritmo polinomial que transforma as instâncias de um para as instâncias da outra com as mesmas respostas. EXPSPACE-completo podem ser vistos como os problemas mais difícieis do universo de problemas em EXPSPACE.

EXPSPACE é um conjunto que engloba PSPACE, NP, and P e acredita-se que também englobe EXPTIME.

Um exemplo de problema EXPSPACE-completo é o problema de reconhecer se duas expressões regulares reperesentam linguagens diferentes, quando a expressão é limitada para quatro operadores: União, Concatenação, Estrela, ou Quadrado.

Se Estrela não for considerada, então o problema se torna NEXPTIME-completo, que é tal como EXPTIME-complete, exceto pelo fato de ser definido em termos de uma máquina de Turing não determinística em vez de uma determinística.

Também foi mostrado por L. Berman em 1980 que o problema de verificar/falsificar qualquer clausula da lógica de primeira ordem sobre números reais que envolva adição ou comparação (mas não multiplicação) também está em EXPSPACE.

Bibliografia

• Michael Sipser (2006). «Sections 8.14&ndash». Introdução à Teoria da Computação. [S.l.]: THOMSON. pp. 327–328. ISBN 0-534-95097-3 

Ligação externa

• Qwiki Stanford (em inglês)