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 · Nederlands
In de complexiteitstheorie is DTIME(f(n)), ook bekend als TIME(f(n)), een die alle beslissingsproblemen bevat die in O(f(n)) tijd opgelost kunnen worden door een deterministische turingmachine. Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van DTIME. Zo kan P gedefinieerd worden als en als . In verhouding tot NTIME geldt dat DTIME(f(n)) ⊆ NTIME(f(n)) voor elke functie f(n) aangezien de benodigde tijd op een niet-deterministische turingmachine die geen niet-determinisme gebruikt gelijk is aan een deterministische turingmachine.
Abstract from DBpedia / Wikipedia · CC BY-SA