DSPACE

from Wikipedia, the free encyclopedia

The term DSPACE comes from the complexity theory in theoretical computer science. It provides a basic statement about the memory requirements that a calculation method on an idealized model of a computer requires. In this way, the memory requirements for certain applications can be estimated.

If, for example, the memory requirement of a calculation method increases in linear proportion with the length of the input value, then the method is said to belong to DSPACE (n) . If the memory requirement grows exponentially with the length of the input value, then the procedure belongs to DSPACE (exp (n)) .

DSPACE (f) or SPACE (f) for short stands for the set of space complexity classes in relation to a deterministic Turing machine . If a concrete function f is given, this means: DSPACE (f) is the class of those decision problems that can be solved on a deterministic Turing machine with O (f) storage space. Note that when specifying a specific function f, the designation DSPACE (f) stands for a single complexity class, while when using an unspecified function f, the designation DSPACE (f) means a large number of complexity classes. In addition, one usually ignores constant factors in the function definition of f and thus sets DSPACE (f) = DSPACE (O (f)).

The notation DSPACE (f) is particularly often used to define more specific complexity classes: For example, the important class PSPACE is defined as follows:

.