EXPSPACE

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2011)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto.
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

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(2p(n)) onde p(n) é uma função polinomial de n. (Alguns autores restringem p(n) para uma função linear, mais 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. 1

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.

Referências[editar | editar código-fonte]

  1. Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.