NTIME

Na teoria da complexidade computacional, a classe de complexidade NTIME(f(n)) é o conjunto dos problemas de decisão que podem ser solucionado por uma máquina de Turing não-determinística usando um tempo O(f(n)) e espaço ilimitado.

A classe de complexidade NP pode ser definida em termos de NTIME da seguinte forma:

$\text{NP}=\bigcup _{k\in \mathbb{N}}\text{NTIME}(n^k)$

Similarmente, a classe NEXP é pode ser definida em termos de NTIME da seguinte forma:

$\text{NEXP}=\bigcup _{k\in \mathbb{N}}\text{NTIME}(2^{n^k})$

O não-determinístico teorema da hierarquia do tempo diz que máquinas não-determinísticas podem solucionar mais problemas assintoticamente em mais tempo.

NTIME também está relacionado com DSPACE da seguinte forma. Para qualquer função de tempo construtível t(n), temos que:

$\text{NTIME}(t(n))\subseteq \text{DSPACE}(t(n))$.

Bibliografia

• Predefinição:Citar livro

Ligação externa

• Predefinição:Url Predefinição:En