Mostrar código-fonte de PSPACE

{{Mais notas|data=julho de 2016}}
Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço.

== Definição Formal ==

Se denotamos por SPACE ( t ( n )) , o conjunto de todos os problemas que podem ser resolvidos por máquinas de Turing usando no máximo t ( n ) espaço para alguma função t do tamanho da entrada n , então podemos definir PSPACE formalmente como

<math>\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k)</math>

'''PSPACE''' é um superconjunto {{NT|strict|estrito}} do conjunto de linguagens sensíveis ao contexto .

Acontece que permitir a máquina de Turing ser não-determinística, não adiciona nenhum poder extra. Por causa do [[Teorema de Savitch]] , NPSPACE é equivalente a PSPACE, essencialmente porque uma máquina de Turing determinística pode simular uma máquina de Turing não determinística sem precisar de muito mais espaço (mesmo que ela possa usar muito mais tempo). Além disso, o complemento de todos os problemas em PSPACE também estão em PSPACE, o que significa que Co-PSPACE = PSPACE.

== Relação entre outras classes ==
[[Image:Complexity subsets pspace.svg|200px|thumb|right|A representação da relação entre classes de complexidade]]
As seguintes relações são conhecidas entre '''PSPACE''' e as [[Classes de Complexidade]] NL , '''[[P (complexidade)|P]]''', '''[[NP (complexidade)|NP]]''', PH , EXPTIME e EXPSPACE:
<br><br>
:<math>\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PH} \subseteq \mbox{PSPACE}</math>
:<math>\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}</math>
:<math>\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}</math>
<br>
É conhecido que na primeira e na segunda linha, pelo menos uma das {{NT|containments|inclusões}} devem ser {{NT|strict|estritas}}, mas não se sabe qual. Suspeita-se que todas são {{NT|strict|estritas}}. Um trabalho recente de L. Gordeev e E. H. Haeusler demonstrou que NP = CoNP = PSPACE através da compressão de provas em [[Dedução natural|Dedução Natural]] na Lógica Minimal Implicacional<ref>{{Citar periódico |titulo=Proof Compression and NP Versus PSPACE II |url=https://czasopisma.uni.lodz.pl/bulletin/article/view/8169 |jornal=Bulletin of the Section of Logic |data=2020-08-15 |issn=2449-836X |acessodata=2020-11-27 |doi=10.18778/0138-0680.2020.16 |primeiro=Lew |ultimo=Gordeev |primeiro2=Edward Hermann |ultimo2=Haeusler}}</ref>.

Em outras palavras, as {{NT|containments|inclusões}} na terceira linha são conhecidas como {{NT|strict|estritas}}. A primeira resulta da diagonalização direta (o teorema de hierarquia do espaço, <math>\mbox{NL} \subsetneq \mbox{NPSPACE}</math>) e o fato de que <math>\mbox{PSPACE} = \mbox{NPSPACE}</math> pelo [[Teorema de Savitch]]. O segundo segue simplesmente o teorema de hierarquia espacial.

Os problemas mais difíceis em '''PSPACE''' são os problemas '''PSPACE-Completos'''.

== Outras caracterizações ==
Uma caracterização alternativa de '''PSPACE''' é o conjunto de problemas decidíveis por uma máquina de Turing alternante em tempo polinomial, às vezes chamado '''APTIME''', ou apenas '''AP'''. <br><br>
A caracterização lógica de '''PSPACE''' da teoria da complexidade descritiva é que ela é o conjunto de problemas expressivos em lógica de segunda ordem com a adição de um operador de fechamento transitivo. Um fechamento total transitivo não é necessário; um fechamento comutativo transitivo e formas ainda mais fracas satisfazem. É a adição deste operador que (possivelmente) distingue '''PSPACE''' de '''PH'''.<br><br>
Um resultado importante da teoria da complexidade é que '''PSPACE''' pode ser caracterizado como todas as línguas reconhecidas por um  sistema de prova interativa em particular, o que define a classe  '''IP''' . Nesse sistema, há um poderoso provador tentando convencer um verificador de tempo polinomial aleatório que uma cadeia pertence a linguagem. Isso deve ser capaz de convencer o verificador com alta probabilidade se a cadeia pertence a linguagem, mas não deve ser capaz de convencê-lo, a não ser com baixa probabilidade, se a cadeia não pertence a linguagem.<br><br>
'''PSPACE''' pode ser caracterizada como a classe de complexidade quântica '''QIP'''.<ref>QIP = PSPACE, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, [[John Watrous |John Watrous]] arXiv:0907.4737 (July 2009)</ref>
<br>
== PSPACE-completude ==
Uma linguagem B é '''PSPACE-completo''' se ele estiver em '''PSPACE''' e é '''PSPACE-difícil''', o que significa que para todo A <math>\in</math> PSPACE, A <math>\leq_p</math> B, onde A <math>\leq_p</math> B significa que há uma redução em tempo polinomial de A para B. Problemas '''PSPACE-completo''' são de grande importância ao estudo dos problemas '''PSPACE''' porque eles representam os problemas mais difíceis em '''PSPACE'''. Encontrar uma solução simples para um problema '''PSPACE-completo''' significa que temos uma solução simples para todos os outros problemas em '''PSPACE''' porque todos os problemas '''PSPACE''' poderiam ser reduzidos a um problema '''PSPACE-completo'''. Um problema pode ser '''PSPACE-difícil''', mas não '''PSPACE-completo''' porque pode não estar em '''PSPACE'''. <br>Por exemplo, o [[Problema da parada]] é '''PSPACE-difícil''', mas não '''PSPACE-completo'''.

{{referencias}}

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