Mostrar código-fonte de EXPSPACE

{{sem notas|data=julho de 2011| angola=| arte=| Brasil=| ciência=| geografia=| música=| Portugal=| sociedade=|1=Este artigo ou secção|2=|3=|4=|5=|6=}}
{{mais fontes|data=abril de 2017}}

Em [[Complexidade_computacional|teoria da complexidade]] computacionais, '''EXPSPACE''' é o conjunto de todos os  [[Problema_de_decisão|problemas de decisão]] solúveis por uma [[Máquina_de_Turing|máquina de Turing determinística]] em espaço O(2<sup>''p''(''n'')</sup>) 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|teorema de savitch]].

Em termos de '''[[DSPACE]]''' e '''[[NSPACE]]''', temos que

:<math>\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k}) = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})</math>

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 (complexidade)|NP]]''', and '''[[P (complexidade)|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. <ref>Meyer, A.R. and [[Larry Stockmeyer|L. Stockmeyer]]. [http://people.csail.mit.edu/meyer/rsq.pdf The equivalence problem for regular expressions with squaring requires exponential space]. ''13th IEEE Symposium on Switching and Automata Theory'', Oct 1972, pp.125–129.</ref>

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

{{referencias}}

== Bibliografia ==
* {{citar livro|autor = [[Michael Sipser]] |ano= 2006 |título= Introdução à Teoria da Computação |publicado= THOMSON | isbn = 0-534-95097-3 |capítulo= Sections 8.14&ndash |páginas=327–328 }}

== Ligação externa ==
* {{url|http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#expspace|Qwiki Stanford}} {{en}}

{{Classes de complexidade}}
[[Categoria:Classes de complexidade]]