DTIME

DTIME

In 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).

The resource DTIME is used to define complexity classes, sets of all of the decision problems which can be solved using a certain amount of computation time. If a problem of input size n can require f(n) computation time to solve, we have a complexity class DTIME(f(n)) (or TIME(f(n))). There is no restriction on the amount of memory space used, but there may be restrictions on some other complexity resources (like alternation).

Contents

Complexity classes in DTIME

Many important complexity classes are defined in terms of DTIME, containing all of the problems that can be solved in a certain amount of deterministic time. Any proper complexity function can be used to define a complexity class, but only certain classes are useful to study. In general, we desire our complexity classes to be robust against changes in the computational model, and to be closed under composition of subroutines.

DTIME satisfies the time hierarchy theorem, meaning that asymptotically larger amounts of time always create strictly larger sets of problems.

The well-known complexity class P comprises all of the problems which can be solved in a polynomial amount of DTIME. It can be defined formally as:

\mbox{P} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(n^k)

P is the smallest robust class which includes linear-time problems \mbox{DTIME}\left(n\right) (AMS 2004, Lecture 2.2, pg. 20). P is one of the largest complexity classes considered "computationally feasible".

A much larger class using deterministic time is EXPTIME, which contains all of the problems solvable using a deterministic machine in exponential time. Formally, we have

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

Larger complexity classes can be defined similarly. Because of the time hierarchy theorem, these classes form a strict hierarchy; we know that \mbox{P} \subsetneq \mbox{EXPTIME} , and on up.

Machine model

The exact machine model used to define DTIME can vary without affecting the power of the resource. Results in the literature often use multitape Turing machines, particularly when discussing very small time classes. In particular, a multitape deterministic Turing machine can never provide more than a quadratic time speedup over a singletape machine (Papadimitriou 1994, Thrm. 2.1).

Multiplicative constants in the amount of time used do not change the power of DTIME classes; a constant multiplicative speedup can always be obtained by increasing the number of states in the finite state control. In the statement of Papadimitriou (1994, Thrm. 2.2), for a language 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.

Generalizations

Using a model other than a deterministic Turing machine, there are various generalizations and restrictions of DTIME. For example, if we use a nondeterministic Turing machine, we have the resource NTIME. The relationship between the expressive powers of DTIME and other computational resources are very poorly understood. One of the few known results[1] is

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

for multitape machines. If we use an alternating Turing machine, we have the resource ATIME.

References

  1. ^ Paul Wolfgang, Nick Pippenger, Endre Szemeredi, William Trotter. On determinism versus non-determinism and related problems. doi: 10.1109/SFCS.1983.39

Wikimedia Foundation. 2010.

См. также в других словарях:

  • DTIME — In der Komplexitätstheorie steht DTIME(f) oder auch kurz TIME(f) für die Menge der Zeitkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine. Wird eine konkrete Funktion f angegeben, so bedeutet dies: DTIME(f) ist die Klasse… …   Deutsch Wikipedia

  • DTIME — En teoría de la complejidad computacional, la clase de complejidad DTIME(f(n)) (también llamada TIME(f(n))) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio… …   Wikipedia Español

  • DTIME — En teoría de la complejidad computacional, la clase de complejidad DTIME(f(n)) (también llamada TIME(f(n))) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(f(n)), y espacio… …   Enciclopedia Universal

  • Time hierarchy theorem — In computational complexity theory, the time hierarchy theorems are important statements about time bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example …   Wikipedia

  • Teorema de la jerarquía temporal — En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede …   Wikipedia Español

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… …   Wikipedia

  • Liste von Komplexitätsklassen — Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch,… …   Deutsch Wikipedia

  • Lückensatz von Borodin — Der Lückensatz von Borodin ist ein 1972 von Allan Borodin veröffentlichter Satz der Komplexitätstheorie in der theoretischen Informatik. Er besagt, dass es in der Hierarchie von Komplexitätsklassen beliebig große Lücken gibt. Formal: Für totale,… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»