ESPACE
Encyclopedia
For the car, see Renault Espace
In computational complexity theory
, the complexity class
ESPACE is the set of decision problem
s that can be solved by a deterministic Turing machine in space 2O
(n).
See also EXPSPACE
.
Renault Espace
The Renault Espace is a large MPV from French car-maker Renault. Generations 1-3 were sold under the Renault brand but manufactured by Matra. The current fourth generation model, which seats seven passengers, is an all-Renault product; the Renault Grand Espace is a long-wheelbase version with...
In computational complexity theory
Computational complexity theory
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...
, the complexity class
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:...
ESPACE is the set of decision problem
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. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s that can be solved by a deterministic Turing machine in space 2O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n).
See also EXPSPACE
EXPSPACE
In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n...
.