Question

Sobre a classe PSPACE-completude, analise as afirmativas a seguir:

I. Os problemas PSPACE-completos podem ser vistos como os problemas mais fáceis em PSPACE.

II. Em geral, acredita-se que tais problemas (PSPACE-completos) não pertencem às famosas classes de complexidade P e NP, mas isso ainda é desconhecido.

III. O problema de decisão para gramáticas determinística sensíveis ao contexto é um exemplo de problema PSPACE-completo.

Neste contexto, é correto o que se afirma em:

Escolha uma:
a.
II e III, apenas. Correto

b.
III, apenas.

c.
I e II, apenas.

d.
I, II e III.

e.
II, apenas.

Answer 1

Resposta:

II e III, apenas. Correto

Explicação:

II. Em geral, acredita-se que tais problemas (PSPACE-completos) não pertencem às famosas classes de complexidade P e NP, mas isso ainda é desconhecido.

III. O problema de decisão para gramáticas determinística sensíveis ao contexto é um exemplo de problema PSPACE-completo.

Corrigido pelo ava