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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e94acb198c8b72bf79a694e3bada7f9d3f346e6)
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}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57b180b25bbe66ac1be7ec3e740f0abf75d451f7)
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:
.
Bibliografia
Ligação externa
|
---|
Considerado viável | |
---|
Suspeita inviável | |
---|
Considerado inviável | |
---|
Hierarquias de classe | |
---|
Famílias de classe | |
---|