Question

Na complexidade computacional, as classes de complexidade de espaço definem a quantidade de memória necessária para armazenar as estruturas de dados associadas ao algoritmo, ou seja, resolver um problema computacional com algoritmo.

Com relação as classes computacionais de complexidade de espaço, complete as lacunas da sentença a seguir.

A classe __________ descreve a disponibilidade de memória para uma máquina de Turing, ou seja, representa a memória total que um computador precisa para solucionar um problema. A classe de complexidade __________ classifica os problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística utilizando quantidade logarítmica de espaço de memória. A classe de complexidade __________ é o conjunto de todos os problemas de decisão solucionáveis por uma MT determinística utilizando espaço exponencial O (2p(n)), onde p é uma função da entrada.
Assinale a alternativa que completa as lacunas corretamente.
Escolha uma:
a.
NPSPACE/ PSPACE/ DSPACE.
b.
DSPACE/ L/ EXPSPACE.
c.
DSPACE/ EXPSPACE / NPSPACE.
d.
PSPACE/ NSPACE/ PSPACE.
e.
PSPACE/ L/ EXPSPACE.

Answer 1

Resposta:

DSPACE/ L/ EXPSPACE

Explicação:

Corrigido no AVA