Saltar para o conteúdo

NTIME

Origem: Wikipédia, a enciclopédia livre.


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:

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

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:

.

Ligação externa

[editar | editar código-fonte]