Dtime
Sign in to saveIn computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem).
Article · Português
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).
Abstract from DBpedia / Wikipedia · CC BY-SA