Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Instalar
Acesso mais rápido do que o navegador!
 

E (complexidade)

Índice E (complexidade)

Na teoria da complexidade computacional, a Classe de complexidade E é o conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística em tempo 2O(n) e, portanto, é igual à classe de complexidade DTIME(2O(n)).

3 relações: Linguagem esparsa, Medida de recurso delimitado, NEXPTIME.

Linguagem esparsa

Em teoria da complexidade computacional, uma linguagem esparsa é uma linguagem formal (um conjunto de strings) cujo número de strings de comprimento n na língua é limitada por uma função de polinômio n. São utilizadas principalmente no estudo da relação entre a classe de complexidade NP com outras classes.

Novo!!: E (complexidade) e Linguagem esparsa · Veja mais »

Medida de recurso delimitado

A medida de recurso delimitado de Lutz é uma generalização da Medida de Lebesgue para classes de complexidade.

Novo!!: E (complexidade) e Medida de recurso delimitado · Veja mais »

NEXPTIME

Em teoria da complexidade, NEXPSPACE (também chamada de NEXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing não determinística em espaço O(2p(n)) para uma dada p(n) e espaço ilimitado.

Novo!!: E (complexidade) e NEXPTIME · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »