DTIME

	Email		Print
	Bookmark		Link

DTIME

In computational complexity theory

Computational complexity theory

Computational complexity theory, as a branch of the theory of computation in computer science, investigates the problems related to the Computational resource required for the execution of algorithms , and the inherent difficulty in providing efficient algorithms for specific computational problems....
, DTIME (or TIME) is the computational resource

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems....
of computation time

Computation time

In computational complexity theory, computation time is a measure of how many steps are used by some abstract machine in a particular computation....
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

Computational problem

In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve....
using a certain algorithm

Algorithm

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing....
. 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 class

Complexity class

In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:...
es, sets of all of the decision problem

Decision problem

Discussion

Ask a question about 'DTIME'

Start a new discussion about 'DTIME'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In computational complexity theory

Computational complexity theory

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems....
of computation time

Computation time

Computational problem

In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve....
using a certain algorithm

Algorithm

Complexity class

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters....
s 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

Alternation

Alternation may refer to:*Alternation *Alternation , a variation in the phonological form of a morpheme*Diathesis alternation*Alternation , see Alternating Turing machine...
).

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

Proper complexity function

A proper complexity function is a function f mapping a natural number to a natural number such that:* f is nondecreasing;* there exists a k-string Turing machine M such that on any input of length n, M halts after O steps, uses O space, and outputs f consecutive blanks....
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

Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements proven by Richard Stearns and Juris Hartmanis that ensure the existence of certain "hard" problems which cannot be solved in a given amount of time....
, meaning that asymptotically

Asymptotic analysis

In pure mathematics and applied mathematics, particularly the analysis of algorithms, real analysis, and engineering, asymptotic analysis is a method of describing Limit ing behaviour....
larger amounts of time always create strictly larger sets of problems.

The well-known complexity class P
P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time....
comprises all of the problems which can be solved in a polynomial amount of DTIME. It can be defined formally as:

P is the smallest robust class which includes linear-time problems (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

EXPTIME

In computational complexity theory, the complexity class EXPTIME is the Set of all decision problems solvable by a deterministic Turing machine in big O notation time, where p is a polynomial function of n....
, which contains all of the problems solvable using a deterministic machine in exponential time

Exponential time

In computational complexity theory, exponential time is the computation time of a problem where the time to complete the computation, m, is bounded by an exponential function of the problem size, n....
. Formally, we have

Larger complexity classes can be defined similarly. Because of the time hierarchy theorem, these classes form a strict hierarchy; we know that , 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 TIME(f(n)). Then, for any > 0, L TIME(f'(n)), where f'(n) = 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

NTIME

In computational complexity theory, the complexity class NTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O, and unlimited space....
. The relationship between the expressive powers of DTIME and other computational resources are very poorly understood.