Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (julho de 2011)

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:

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

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

${\displaystyle {\mbox{NEXP}}=\bigcup _{k\in \mathbb {N} }{\mbox{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:

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

• Michael Sipser (2006). «Sections 8.14&ndash». Introdução à Teoria da Computação. [S.l.]: THOMSON. pp. 356–367. ISBN 0-534-95097-3 

• Qwiki Stanford (em inglês)