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:

${\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))}$.

Bibliografia

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

Ligação externa

• Qwiki Stanford (em inglês)