ESPAÇO
Na teoria da complexidade computacional , a classe PSPACE é o conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística em espaço polinomial ( ) e tempo ilimitado.
A definição não depende do caráter determinístico da máquina de Turing (este é um corolário do teorema de Savitch ). Então PSPACE = NPSPACE . Se um problema é resolvido por um algoritmo de complexidade espacial polinomial não determinístico, ele também pode ser resolvido por um algoritmo de complexidade espacial polinomial determinístico.
Definição formal
No caso da complexidade espacial, a classe de linguagens PSPACE pode ser caracterizada :
isto é, a união de todas as classes de complexidade espacial polinomial em Máquinas de Turing determinísticas.
Relação entre outras classes
Todos os problemas solucionáveis em tempo polinomial com máquinas não determinísticas (todos os problemas que estão em NP ) podem ser resolvidos em espaço polinomial, portanto PSPACE inclui NP e Co-NP .
Conjectura-se que existe um conjunto de problemas que são PSPACE-completos . Se houver e um deles estiver em NP , então PSPACE = NP , ou se algum deles estiver em P , então PSPACE = P .
O conjunto PSPACE é um subconjunto estrito do conjunto de linguagens sensíveis ao contexto. As seguintes inclusões foram demonstradas:
NL ⊆ P ⊆ NP ⊆ PSPACE
NL ⊂ PSPACE ⊂ EXPSPACE
PSPACE-completo ⊆ PSPACE
Na primeira linha há três inclusões, e sabe-se que NL ⊂ PSPACE, então pelo menos uma das inclusões é estrita, embora qual ainda não tenha sido descoberta. Todos os três são suspeitos de serem inclusões estritas. Uma solução para o problema de saber se as classes P e NP são distintas vale um milhão de dólares. Suspeita-se também que a inclusão da última linha seja estrita.
Os problemas mais difíceis no PSPACE são os do conjunto completo do PSPACE .
Outros recursos
Uma característica alternativa do PSPACE é o conjunto de problemas decidíveis por uma máquina de Turing alternativa em tempo polinomial , às vezes chamada de APTIME ou apenas AP .
Uma característica lógica do PSPACE da teoria da complexidade descritiva é que eles são conjuntos de problemas expressos em segunda ordem lógica com a adição de um operador de fechamento transitivo . Um fechamento transitivo completo não é necessário; um fechamento transitivo comutativo é suficiente e formas ainda mais fracas. A adição deste operador torna o PSPACE distinguível do PH .
Um resultado importante da teoria da complexidade é que o PSPACE pode ser caracterizado como todas as linguagens reconhecidas pela presença de um sistema de prova interativo, uma definição da classe IP . Neste sistema, há uma prova que tenta convencer aleatoriamente em tempo polinomial a verificar que uma string pertence à linguagem. Ele deve ser capaz de convencer o verificador com alta probabilidade se a string estiver no idioma, mas não deve ser capaz de convencer com baixa probabilidade se a string não estiver no idioma.
NPSPACE
A classe de complexidade NPSPACE é o conjunto de problemas de decisão que podem ser resolvidos em uma máquina de Turing não determinística em espaço polinomial e tempo ilimitado.
Pelo teorema de Savitch , NPSPACE = PSPACE.
Definição formal
Denotando com NSPACE ( t ( n )), o conjunto de todos os problemas que podem ser resolvidos com uma máquina de Turing não determinística usando o espaço O ( t ( n )) para alguma função t sobre o tamanho n da entrada e o limite de tempo sen, NPSPACE pode ser definido formalmente como [ 1 ]
No entanto, permitir o não determinismo na máquina de Turing não adiciona energia adicional, pois reutilizando o espaço, uma máquina de Turing determinística pode simular uma máquina não determinística, embora isso possa levar muito mais tempo. [ 2 ]
