NTIME

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2011)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.


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:

\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:

\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:

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

Referências[editar | editar código-fonte]