Question

Na teoria da complexidade computacional, o teorema de Savitch, provado por Walter Savitch em 1970, afirma que a classe NPSPACE é equivalente a PSPACE. Por que isto ocorre?

Assinale a alternativa correta.

Escolha uma:
a. Porque uma máquina de Turing não-determinística pode simular uma máquina de Turing determinística.

b. Porque PSPACE(sNão) é fechada sob a complementação para qualquer função.

c. Porque são conjuntos de problemas expressivos em lógica de segunda ordem com a adição de um operador de fechamento transitivo.

d. Porque NSPACE(sNão) é fechada sob a complementação para qualquer função.

e. 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).

Answer 1

Resposta:

O correto é a Letra e. 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).

Explicação: