Question

Considere a seguinte definição:

"Uma linguagem B é PSPACE-completa se ela satisfaz duas condições:
1. B está em PSPACE, e
2. toda linguagem A em PSPACE é ____________ em tempo ____________ a B."

Assinale a alternativa que preenche corretamente as lacunas.

Escolha uma:
a. redutível / exponencial
b. solúvel / exponencial
c. insolúvel / polinomial
d. solúvel / recursivo
e. redutível / polinomial

Answer 1

Resposta:

Letra E

Explicação:

PSPACE é redutível / polinomial.