Dtime

Na teoria da complexidade computacional, DTIME (ou TIME) é o recurso computacional de tempo de computação para uma máquina de Turing determinística. Ela representa a quantidade de tempo (ou número de passos de cálculo) que um computador "normal" físico seria necessário para resolver um determinado problema computacional usando um certo algoritmo. É um dos mais bem estudado recursos complexidade, porque corresponde tão intimamente a um recurso importante do mundo real (a quantidade de tempo que leva um computador para resolver um problema).

O recurso DTIME é usado para definir classes de complexidade, conjuntos de todos os problemas de decisão que podem ser resolvidos usando uma certa quantidade de tempo de computação. Se um problema de tamanho da entrada n pode exigir tempo de computação f (n) para resolver, temos uma classe de complexidade DTIME (f (n)) (ou TIME (f (n))). Não há nenhuma restrição sobre a quantidade de espaço de memória usado, mas pode haver restrições em alguns outros recursos de complexidade (como alternância).

Classes de complexidade em DTIME

Muitas classes de complexidade importantes são definidas em termos de DTIME, contendo todos os problemas que podem ser resolvidos em um determinado período de tempo determinístico. Qualquer função de complexidade adequada pode ser usado para definir uma classe de complexidade, mas apenas certas classes são úteis para estudo. Em geral, desejamos nossas aulas de complexidade para ser robusto contra mudanças no modelo computacional, e para ser fechado sob a composição de sub-rotinas.

DTIME satisfaz o teorema de hierarquia de tempo, o que significa que, assintoticamente, quantidades maiores de tempo sempre criam conjuntos estritamente maiores de problemas.

A conhecida classe de complexidade P é composta por todos os problemas que podem ser resolvidos em uma quantidade polinomial de DTIME. Pode ser definido formalmente como:

${\mbox{P}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}(n^{k})$

P é a menor classe robusta que inclui de tempo linear problemas ${\mbox{DTIME}}\left(n\right)$. P é uma das maiores classes de complexidade que pode ser considerada "computacionalmente viável".

Uma classe muito maior usando o tempo determinístico é EXPTIME, que contém todos os problemas podem ser resolvidos usando uma máquina determinística em tempo exponencial. Formalmente, temos

${\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).$

Classes de maior complexidade podem ser definidos de forma semelhante. Por causa do teorema de hierarquia de tempo, essas classes formam uma hierarquia rígida, sabemos que ${\mbox{P}}\subsetneq {\mbox{EXPTIME}}$.

Modelo de Máquina

O modelo exato da máquina usada para definir DTIME pode variar sem afetar o poder do recurso. Resultados na literatura muitas vezes usam Máquinas de Turing Multifita, particularmente quando se discute as aulas em tempo muito pequeno. Em particular, uma máquina de Turing determinística Multifita nunca pode fornecer mais do que uma aceleração do tempo quadrático sobre uma máquina de única fita. (Papadimitriou 1994, THRM. 2.1).

Constantes multiplicativas na quantidade de tempo utilizada não mudam o poder das classes DTIME; um aumento de velocidade constante multiplicativo sempre podem ser obtidos através do aumento do número de estados no controle de estados finitos. Na declaração de Papadimitriou (1994, THRM. 2.2), para uma linguagem L,

Let L $\in$ DTIME(f(n)). Then, for any $\epsilon$ > 0, L $\in$ DTIME(f'(n)), where f'(n) = $\epsilon$ f(n) n 2.

Generalizações

Usando um modelo diferente de uma máquina de Turing determinística, existem várias generalizações e restrições de DTIME. Por exemplo, se usarmos uma máquina de Turing não determinística, temos o recurso NTIME. A relação entre os poderes expressivos da DTIME e outros recursos computacionais são muito pouco compreendidos. Um dos poucos resultados conhecidos é

${\mathsf {DTIME}}(O(n))\neq {\mathsf {NTIME}}(O(n))$

para máquinas Multifita. Se usarmos uma máquina de Turinga alternada, temos o recurso ATIME.

Bibliografia

• American Mathematical Society (2004). Rudich, Steven and Avi Wigderson (ed.), ed. Computational Complexity Theory. [S.l.]: American Mathematical Society and Institute for Advanced Study. ISBN 0-8218-2872-X 
• Papadimitriou, Christos H. (1994). Computational Complexity. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1