NTIME

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Text document with red question mark.svg
Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações (desde julho de 2011). Ajude a melhorar este artigo inserindo fontes.


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:

.

Bibliografia[editar | editar código-fonte]

Ligação externa[editar | editar código-fonte]